Jelle Hellings

Assistant professor
Department of Computing and Software
McMaster University.

My research is centered around novel directions for high-performance large-scale data management systems. My research has a strong theoretical component (e.g., lower bound results, finite model theory, dependency theory) and a strong algorithmic component (e.g., external-memory algorithms, distributed algorithms, join algorithms). Currently, my focus is on the development of scalable resilient systems that can manage data and processing complex transactions, while providing strong guarantees toward users in the presence of faulty behavior (e.g., hardware failures, software failures, and malicious attacks).

Previously, I was a Postdoc Scholar in the Exploratory Systems Lab at the Computer Science Department of the University of California, Davis, where I worked on scalable resilient distributed data processing under the supervision of Mohammed Sadoghi. I did my doctoral training in the Databases and Theoretical Computer Science research group at Hasselt University under the supervision of Marc Gyssens. During my doctoral training, I worked on semi-structured data with a main focus on graph databases (e.g., graph query languages, constraints on graph data, graph query evaluation algorithms). Finally, I did my Bachelor and Master in computer science and engineering at the Eindhoven University of Technology, where my final Master project focused on external-memory algorithms for indexing very large graph datasets.

I refer to a recent Postdoc Spotlight for some further background on me and my work.

Publications (Export citations as BibTeX)

Jump to Books, Journal Papers, Conference Proceedings, Tutorials, Demos, and Talks, Theses.

Books

  1. MC 2021.
    Fault-tolerant distributed transactions on blockchain. Suyash Gupta, Jelle Hellings, and Mohammad Sadoghi. (2021). In: Synthesis Lectures on Data Management. Morgan & Claypool. DOI: 10.2200/S01068ED1V01Y202012DTM065.
    Abstract

    Since the introduction of Bitcoin--the first widespread application driven by blockchain--the interest of the public and private sectors in blockchain has skyrocketed. In recent years, blockchain-based fabrics have been used to address challenges in diverse fields such as trade, food production, property rights, identity-management, aid delivery, health care, and fraud prevention.

    These fundamental concepts and the technologies behind them--a generic ledger-based data model, cryptographically ensured data integrity, and consensus-based replication--prove to be a powerful and inspiring combination, a catalyst to promote computational trust. In this book, we present an in-depth study of blockchain, unraveling its revolutionary promise to instill computational trust in society, all carefully tailored to a broad audience including students, researchers, and practitioners. We offer a comprehensive overview of theoretical limitations and practical usability of consensus protocols while examining the diverse landscape of how blockchains are manifested in their permissioned and permissionless forms.

Journal Papers

  1. VLDB 2021.
    ByShard: Sharding in a Byzantine environment. Jelle Hellings and Mohammad Sadoghi. (2021). In: Proceedings of the VLDB Endowment, 14(11), 2230-2243. VLDB. DOI: 10.14778/3476249.3476275.
    author copy, slides, poster, project page.
    Video Presentation
    Abstract

    The emergence of blockchains has fueled the development of resilient systems that can deal with Byzantine failures due to crashes, bugs, or even malicious behavior. Recently, we have also seen the exploration of sharding in these resilient systems, this to provide the scalability required by very large data-based applications. Unfortunately, current sharded resilient systems all use system-specific specialized approaches toward sharding that do not provide the flexibility of traditional sharded data management systems.To improve on this situation, we fundamentally look at the design of sharded resilient systems. We do so by introducing ByShard, a unifying framework for the study of sharded resilient systems. Within this framework, we show how two-phase commit and two-phase locking--two techniques central to providing atomicity and isolation in traditional sharded databases--can be implemented efficiently in a Byzantine environment, this with a minimal usage of costly Byzantine resilient primitives. Based on these techniques, we propose eighteen multi-shard transaction processing protocols. Finally, we practically evaluate these protocols and show that each protocol supports high transaction throughput and provides scalability while each striking its own trade-off between throughput, isolation level, latency, and abort rate. As such, our work provides a strong foundation for the development of ACID-compliant general-purpose and flexible sharded resilient data management systems.

  2. CJ 2020.
    From relation algebra to semi-join algebra: An approach to graph query optimization. Jelle Hellings, Catherine L. Pilachowski, Dirk Van Gucht, Marc Gyssens, and Yuqing Wu. (2020). In: The Computer Journal, 64(5), 789--811. Oxford University Press. DOI: 10.1093/comjnl/bxaa031. See also DBPL 2017, PhD thesis.
    author copy.
    Abstract

    Many graph query languages rely on composition to navigate graphs and select nodes of interest, even though evaluating compositions of relations can be costly. Often, this need for composition can be reduced by rewriting towards queries using semi-joins instead, resulting in a significant reduction of the query evaluation cost. We study techniques to recognize and apply such rewritings. Concretely, we study the relationship between the expressive power of the relation algebras, which heavily rely on composition, and the semi-join algebras, which replace composition in favor of semi-joins. Our main result is that each fragment of the relation algebras where intersection and/or difference is only used on edges (and not on complex compositions) is expressively equivalent to a fragment of the semi-join algebras. This expressive equivalence holds for node queries evaluating to sets of nodes. For practical relevance, we exhibit constructive rules for rewriting relation algebra queries to semi-join algebra queries, and prove that they lead to only a well-bounded increase in the number of steps needed to evaluate the rewritten queries. In addition, on sibling-ordered trees, we establish new relationships among the expressive power of Regular XPath, Conditional XPath, FO-logic, and the semi-join algebra augmented with restricted fixpoint operators.

  3. VLDB 2020.
    ResilientDB: global scale resilient blockchain fabric. Suyash Gupta, Sajjad Rahnama, Jelle Hellings, and Mohammad Sadoghi. (2020). In: Proceedings of the VLDB Endowment, 13(6), 868-883. VLDB. DOI: 10.14778/3380750.3380757. See also FAB 2020.
    author copy, technical report, video by Suyash Gupta.
    Abstract

    Recent developments in blockchain technology have inspired innovative new designs in resilient distributed and database systems. At their core, these blockchain applications typically use Byzantine fault-tolerant consensus protocols to maintain a common state across all replicas, even if some replicas are faulty or malicious. Unfortunately, existing consensus protocols are not designed to deal with geo-scale deployments in which many replicas spread across a geographically large area participate in consensus.

    To address this, we present the Geo-Scale Byzantine Fault-Tolerant consensus protocol (GeoBFT). GeoBFT is designed for excellent scalability by using a topological-aware grouping of replicas in local clusters, by introducing parallelization of consensus at the local level, and by minimizing communication between clusters. To validate our vision of high-performance geo-scale resilient distributed systems, we implement GeoBFT in our efficient ResilientDB permissioned blockchain fabric. We show that GeoBFT is not only sound and provides great scalability, but also outperforms state-of-the-art consensus protocols by a factor of six in geo-scale deployments.

  4. IS 2020.
    Comparing the expressiveness of downward fragments of the relation algebra with transitive closure on trees. Jelle Hellings, Marc Gyssens, Yuqing Wu, Dirk Van Gucht, Jan Van den Bussche, Stijn Vansummeren, and George H. L. Fletcher. (2020). In: Information Systems, 89. Elsevier. DOI: 10.1016/j.is.2019.101467. See also DBPL 2015, PhD thesis.
    author copy, technical report, project page.
    Abstract

    Motivated by the continuing interest in the tree data model, we study the expressive power of downward navigational query languages on trees and chains. Basic navigational queries are built from the identity relation and edge relations using composition and union. We study the effects on relative expressiveness when we add transitive closure, projections, coprojections, intersection, and difference; this for boolean queries and path queries on labeled and unlabeled structures. In all cases, we present the complete Hasse diagram. In particular, we establish, for each query language fragment that we study on trees, whether it is closed under difference and intersection.

  5. AMAI 2019.
    First-order definable counting-only queries. Jelle Hellings, Marc Gyssens, Dirk Van Gucht, and Yuqing Wu. (2019). In: Annals of Mathematics and Artificial Intelligence, 87, 109-136. Springer. DOI: 10.1007/s10472-019-09652-8. See also FoIKS 2018b.
    author copy.
    Abstract

    Many data sources can be represented easily by collections of sets of objects. For several practical queries on such collections of sets of objects, the answer does not depend on the precise composition of these sets, but only on the number of sets to which each object belongs. This is the case k = 1 for the more general situation where the query answer only depends on the number of sets to which each collection of at most k objects belongs. We call such queries k-counting-only. Here, we focus on k-SyCALC, i.e., k-counting-only queries that are first-order definable. As k-SyCALC is semantically defined, however, it is not surprising that it is already undecidable whether a first-order query is in 1-SyCALC. Therefore, we introduce SimpleCALC-k, a syntactically defined (strict) fragment of k-SyCALC. It turns out that many practical queries in k-SyCALC can already be expressed in SimpleCALC-k. We also define the query language GCount-k, which expresses counting-only queries directly by using generalized counting terms, and show that this language is equivalent to SimpleCALC-k. We prove that the k-counting-only queries form a non-collapsing hierarchy: for every k, there exist (k+1)-counting-only queries that are not k-counting-only. This result specializes to both SimpleCALC-k and k-SyCALC. Finally, we establish a strong dichotomy between 1-SyCALC and SimpleCALC-k on the one hand and 2-SyCALC on the other hand by showing that satisfiability, validity, query containment, and query equivalence are decidable for the former two languages, but not for the latter one.

  6. JCSS 2019.
    Calculi for symmetric queries. Marc Gyssens, Jelle Hellings, Jan Paredaens, Dirk Van Gucht, Jef Wijsen, Yuqing Wu. (2019). In: Journal of Computer and System Sciences, 105, 54-86. Elsevier. DOI: 10.1016/j.jcss.2019.04.003.
    author copy.
    Abstract

    Symmetric queries are introduced as queries on a sequence of sets of objects the result of which does not depend on the order of the sets. An appropriate data model is proposed, and two query languages are introduced, QuineCALC and SyCALC. They are correlated with the symmetric Boolean functions of Quine, respectively symmetric relational functions. The former correlation yields an incidence-based normal form for QuineCALC queries. More generally, we propose counting-only queries as those SyCALC queries the result of which only depends on incidence information, and characterize them as quantified Boolean combinations of QuineCALC queries. A normal form is proposed for them too. It is shown that, while it is undecidable whether a SyCALC query is counting-only, it is decidable whether a counting-only query is a QuineCALC query. Finally, some classical decidability problems are considered which are shown to be undecidable for SyCALC, but decidable for QuineCALC and counting-only queries.

  7. AMAI 2016.
    Implication and axiomatization of functional and constant constraints. Jelle Hellings, Marc Gyssens, Jan Paredaens, Yuqing Wu. (2016). In: Annals of Mathematics and Artificial Intelligence, 76(3), 251-279. Springer. DOI: 10.1007/s10472-015-9473-7. See also FoIKS 2014.
    author copy.
    Abstract

    Akhtar et al. introduced equality-generating constraints and functional constraints as a first step towards dependency-like integrity constraints for RDF data. Here, we focus on functional constraints. Since the usefulness of functional constraints is not limited to the RDF data model, we study the functional constraints in the more general setting of relations with arbitrary arity. We further introduce constant constraints and study the functional and constant constraints combined.

    Our main results are sound and complete axiomatizations for the functional and constant constraints, both separately and combined. These axiomatizations are derived using the chase algorithm for equality-generating constraints. For derivations of constant constraints, we show how every chase step can be simulated by a bounded number of applications of inference rules. For derivations of functional constraints, we show that the chase algorithm can be normalized to a more specialized symmetry-preserving chase algorithm performing so-called symmetry-preserving steps. We then show how each symmetry-preserving step can be simulated by a bounded number of applications of inference rules. The axiomatization for functional constraints is in particular applicable to the RDF data model, solving a major open problem of Akhtar et al.

Conference Proceedings (peer-reviewed)

  1. EDBT 2021.
    Proof-of-Execution: Reaching consensus through fault-tolerant speculation. Suyash Gupta, Sajjad Rahnama, Jelle Hellings, and Mohammad Sadoghi. (2021). In: Proceedings of the 24th International Conference on Extending Database Technology (EDBT), 301-312. OpenProceedings.org. DOI: 10.5441/002/edbt.2021.27.
    author copy, video by Suyash Gupta.
    Abstract

    Multi-party data management and blockchain systems require data sharing among participants. To provide resilient and consistent data sharing, transactions engines rely on Byzantine Fault-Tolerant consensus (BFT), which enables operations during failures and malicious behavior. Unfortunately, existing BFT protocols are unsuitable for high-throughput applications due to their high computational costs, high communication costs, high client latencies, and/or reliance on twin-paths and non-faulty clients.

    In this paper, we present the Proof-of-Execution consensus protocol (PoE) that alleviates these challenges. At the core of PoE are out-of-order processing and speculative execution, which allow PoE to execute transactions before consensus is reached among the replicas. With these techniques, PoE manages to reduce the costs of BFT in normal cases, while guaranteeing reliable consensus for clients in all cases. We envision the use of PoE in high-throughput multi-party data-management and blockchain systems. To validate this vision, we implement PoE in our efficient ResilientDB fabric and extensively evaluate PoE against several state-of-the-art BFT protocols. Our evaluation showcases that PoE achieves up-to-80% higher throughputs than existing BFT protocols in the presence of failures.

  2. ICDE 2021.
    RCC: Resilient concurrent consensus for high-throughput secure transaction processing. Suyash Gupta, Jelle Hellings, and Mohammad Sadoghi. (2021). In: 2021 IEEE 37th International Conference on Data Engineering (ICDE), 1392-1403. IEEE. DOI: 10.1109/ICDE51399.2021.00124.
    author copy, video by Suyash Gupta.
    Abstract

    Recently, we saw the emergence of consensus-based database systems that promise resilience against failures, strong data provenance, and federated data management. Typically, these fully-replicated systems are operated on top of a primary-backup consensus protocol, which limits the throughput of these systems to the capabilities of a single replica (the primary).

    To push throughput beyond this single-replica limit, we propose concurrent consensus. In concurrent consensus, replicas independently propose transactions, thereby reducing the influence of any single replica on performance. To put this idea in practice, we propose our RCC paradigm that can turn any primary-backup consensus protocol into a concurrent consensus protocol by running many consensus instances concurrently. RCC is designed with performance in mind and requires minimal coordination between instances. Furthermore, RCC also promises increased resilience against failures. We put the design of RCC to the test by implementing it in ResilientDB, our high-performance resilient blockchain fabric, and comparing it with state-of-the-art primary-backup consensus protocols. Our experiments show that RCC achieves up to 2.75 times higher throughput than other consensus protocols and can be scaled to 91 replicas.

  3. TIME 2020.
    Stab-Forests: Dynamic Data Structures for Efficient Temporal Query Processing. Jelle Hellings and Yuqing Wu. (2020). In: 27th International Symposium on Temporal Representation and Reasoning (TIME 2020), 18:1-18:19. Schloss Dagstuhl. DOI: 10.4230/LIPIcs.TIME.2020.18.
    author copy, slides, project page.
    Video Presentation
    Abstract

    Many sources of data have temporal start and end attributes or are created in a time-ordered manner. Hence, it is only natural to consider joining datasets based on these temporal attributes. To do so efficiently, several internal-memory temporal join algorithms have recently been proposed. Unfortunately, these join algorithms are designed to join entire datasets and cannot efficiently join skewed datasets in which only few events participate in the join result.

    To support high-performance internal-memory temporal joins of skewed datasets, we propose the skip-join algorithm, which operates on stab-forests. The stab-forest is a novel dynamic data structure for indexing temporal data that allows efficient updates when events are appended in a time-based order. Our stab-forests efficiently support not only traditional temporal stab-queries, but also more general multi-stab-queries. We conducted an experimental evaluation to compare the skip-join algorithm with state-of-the-art techniques using real-world datasets. We observed that the skip-join algorithm outperforms other techniques by an order of magnitude when joining skewed datasets and delivers comparable performance to other techniques on non-skewed datasets.

  4. LSGDA 2020.
    Explaining results of path queries on graphs. Jelle Hellings. (2020). In: Software Foundations for Data Interoperability and Large Scale Graph Data Analytics, 84-98. Springer. DOI: 10.1007/978-3-030-61133-0_7.
    author copy, technical report, slides, project page.
    Video Presentation
    Abstract

    Many graph query languages use, at their core, path queries that yield node pairs that are connected by a path of interest. For the end-user, such node pairs only give limited insight as to why this query result is obtained, as the pair does not directly identify the underlying path of interest. To address this limitation of path queries, we propose the single-path semantics, which evaluates path queries to, for each node pair (m,n), a single path from m to n satisfying the conditions of the query. To put our proposal in practice, we provide an efficient algorithm for evaluating context-free path queries, a particular powerful type of path queries, using the single-path semantics. Additionally, we perform a short evaluation of our techniques that shows that the single-path semantics is practically feasible, even when query results grow large.

  5. ICDT 2020.
    Coordination-free Byzantine replication with minimal communication costs. Jelle Hellings and Mohammad Sadoghi. (2020). In: 23rd International Conference on Database Theory (ICDT 2020), 17:1-17:20. Schloss Dagstuhl. DOI: 10.4230/LIPIcs.ICDT.2020.17.
    author copy, slides, video.
    Video Presentation
    Abstract

    State-of-the-art fault-tolerant and federated data management systems rely on fully-replicated designs in which all participants have equivalent roles. Consequently, these systems have only limited scalability and are ill-suited for high-performance data management. As an alternative, we propose a hierarchical design in which a Byzantine cluster manages data, while an arbitrary number of learners can reliable learn these updates and use the corresponding data.

    To realize our design, we propose the delayed-replication algorithm, an efficient solution to the Byzantine learner problem that is central to our design. The delayed-replication algorithm is coordination-free, scalable, and has minimal communication cost for all participants involved. In doing so, the delayed-broadcast algorithm opens the door to new high-performance fault-tolerant and federated data management systems. To illustrate this, we show that the delayed-replication algorithm is not only useful to support specialized learners, but can also be used to reduce the overall communication cost of permissioned blockchains and to improve their storage scalability.

  6. DISC 2019a.
    Brief announcement: The fault-tolerant cluster-sending problem. Jelle Hellings and Mohammad Sadoghi. (2019). In: 33rd International Symposium on Distributed Computing (DISC 2019), 45:1-45:3. Schloss Dagstuhl. DOI: 10.4230/LIPIcs.DISC.2019.45.
    author copy, technical report, slides.
    Abstract

    The development of fault-tolerant distributed systems that can tolerate Byzantine behavior has traditionally been focused on consensus protocols, which support fully-replicated designs. For the development of more sophisticated high-performance Byzantine distributed systems, more specialized fault-tolerant communication primitives are necessary, however.

    In this brief announcement, we identify the cluster-sending problem--the problem of sending a message from one Byzantine cluster to another Byzantine cluster in a reliable manner--as such an essential communication primitive. We not only formalize this fundamental problem, but also establish lower bounds on the complexity of this problem under crash failures and Byzantine failures. Furthermore, we develop practical cluster-sending protocols that meet these lower bounds and, hence, have optimal complexity. As such, our work provides a strong foundation for the further exploration of novel designs that address challenges encountered in fault-tolerant distributed systems.

  7. DISC 2019b.
    Brief announcement: Revisiting consensus protocols through wait-free parallelization. Suyash Gupta, Jelle Hellings, and Mohammad Sadoghi. (2019). In: 33rd International Symposium on Distributed Computing (DISC 2019), 44:1-44:3. Schloss Dagstuhl. DOI: 10.4230/LIPIcs.DISC.2019.44. See also ICDE 2021.
    author copy, technical report, slides.
    Abstract

    In this brief announcement, we propose a protocol-agnostic approach to improve the design of primary-backup consensus protocols. At the core of our approach is a novel wait-free design of running several instances of the underlying consensus protocol in parallel. To yield a high-performance parallelized design, we present coordination-free techniques to order operations across parallel instances, deal with instance failures, and assign clients to specific instances. Consequently, the design we present is able to reduce the load on individual instances and primaries, while also reducing the adverse effects of any malicious replicas. Our design is fine-tuned such that the instances coordinated by non-faulty replicas are wait-free: they can continuously make consensus decisions, independent of the behavior of any other instances.

  8. FoIKS 2018a.
    The power of tarski's relation algebra on trees. Jelle Hellings, Yuqing Wu, Marc Gyssens, and Dirk Van Gucht. (2018). In: Foundations of Information and Knowledge Systems, 244-264. Springer. DOI: 10.1007/978-3-319-90050-6_14. See also PhD thesis.
    author copy, slides, project page.
    Abstract

    Fragments of Tarski's relation algebra form the basis of many versatile graph and tree query languages including the regular path queries, XPath, and SPARQL. Surprisingly, however, a systematic study of the relative expressive power of relation algebra fragments on trees has not yet been undertaken. Our approach is to start from a basic fragment which only allows composition and union. We then study how the expressive power of the query language changes if we add diversity, converse, projections, coprojections, intersections, and/or difference, both for path queries and Boolean queries. For path queries, we found that adding intersection and difference yields more expressive power for some fragments, while adding one of the other operators always yields more expressive power. For Boolean queries, we obtain a similar picture for the relative expressive power, except for a few fragments where adding converse or projection yields no more expressive power. One challenging problem remains open, however, for both path and Boolean queries: does adding difference yields more expressive power to fragments containing at least diversity, coprojections, and intersection?

  9. FoIKS 2018b.
    First-order definable counting-only queries. Jelle Hellings, Marc Gyssens, Dirk Van Gucht, and Yuqing Wu. (2018). In: Foundations of Information and Knowledge Systems, 225-243. Springer. DOI: 10.1007/978-3-319-90050-6_13. See also AMAI 2019.
    author copy, slides.
    Abstract

    For several practical queries on bags of sets of objects, the answer does not depend on the precise composition of these sets, but only on the number of sets to which each object belongs. This is the case k=$1$ for the more general situation where the query answer only depends on the number of sets to which each group of at most k objects belongs. We call such queries k-counting-only. Here, we focus on k-SyCALC, k-counting-only queries that are first-order definable. As k-SyCALC is semantically defined, however, it is not surprising that it is already undecidable whether a first-order query is in 1-SyCALC. Therefore, we introduce SimpleCALC-k, a syntactically defined (strict) fragment of k-SyCALC. It turns out that many practical queries in k-SyCALC can already be expressed in SimpleCALC-k. We prove that the k-counting-only queries form a non-collapsing hierarchy: for every k, there exist (k+1)-counting-only queries that are not k-counting-only. This result specializes to both SimpleCALC-k and k-SyCALC. Finally, we establish a strong dichotomy between 1-SyCALC and SimpleCALC-k on the one hand and 2-SyCALC on the other hand by showing that satisfiability, validity, query containment, and query equivalence are decidable for the former two languages, but not for the latter one.

  10. DBPL 2017.
    From relation algebra to semi-join algebra: An approach for graph query optimization. Jelle Hellings, Catherine L. Pilachowski, Dirk Van Gucht, Marc Gyssens, and Yuqing Wu. (2017). In: Proceedings of The 16th International Symposium on Database Programming Languages, 5:1-5:10. ACM. DOI: 10.1145/3122831.3122833. See also CJ 2020, PhD thesis.
    author copy, slides.
    Abstract

    Many graph query languages rely on the composition operator to navigate graphs and select nodes of interests, even though evaluating compositions of relations can be costly. Often, this need for composition can be reduced by rewriting towards queries that use semi-joins instead. In this way, the cost of evaluating queries can be significantly reduced.

    We study techniques to recognize and apply such rewritings. Concretely, we study the relationship between the expressive power of the relation algebras, that heavily rely on composition, and the semi-join algebras, that replace the composition operator in favor of the semi-join operators.

    As our main result, we show that each fragment of the relation algebras where intersection and/or difference is only used on edges (and not on complex compositions) is expressively equivalent to a fragment of the semi-join algebras. This expressive equivalence holds for node queries that evaluate to sets of nodes. For practical relevance, we exhibit constructive steps for rewriting relation algebra queries to semi-join algebra queries, and prove that these steps lead to only a well-bounded increase in the number of steps needed to evaluate the rewritten queries.

    In addition, on node-labeled graphs that are sibling-ordered trees, we establish new relationships among the expressive power of Regular XPath, Conditional XPath, FO-logic, and the semi-join algebra augmented with restricted fixpoint operators.

  11. DBPL 2015.
    Relative expressive power of downward fragments of navigational query languages on trees and chains. Jelle Hellings, Marc Gyssens, Yuqing Wu, Dirk Van Gucht, Jan Van den Bussche, Stijn Vansummeren, and George H. L. Fletcher. (2015). In: Proceedings of the 15th Symposium on Database Programming Languages, 59-68. ACM. DOI: 10.1145/2815072.2815081. See also IS 2020, PhD thesis.
    author copy, slides, project page.
    Abstract

    Motivated by the continuing interest in the tree data model, we study the expressive power of downward fragments of navigational query languages on trees. The basic navigational query language we consider expresses queries by building binary relations from the edge relations and the identity relation, using composition and union. We study the effects on the expressive power when we add transitive closure, projections, coprojections, intersection, and difference. We study expressiveness at the level of boolean queries and path queries, on labeled and unlabeled trees, and on labeled and unlabeled chains. In all these cases, we are able to present the complete Hasse diagram of relative expressiveness. In particular, we were able to decide, for each fragment of the navigational query languages that we study, whether it is closed under difference and intersection when applied on trees.

  12. ICDT 2014.
    Conjunctive context-free path queries. Jelle Hellings. (2014). In: Proceedings of the 17th International Conference on Database Theory (ICDT), 119-130. OpenProceedings.org. DOI: 10.5441/002/icdt.2014.15.
    author copy, slides.
    Abstract

    In graph query languages, regular expressions are commonly used to specify the labeling of paths. A natural step in increasing the expressive power of these query languages is replacing regular expressions by context-free grammars. With the Conjunctive Context-Free Path Queries (CCFPQ) we introduce such a language based on the well-known Conjunctive Regular Path Queries (CRPQ).

    First, we show that query evaluation of CCFPQ has polynomial time data complexity. Secondly, we look at the generalization of regular expressions, as used in CRPQ, to regular relations and show how similar generalizations can be applied to context-free grammars, as used in CCFPQ. Thirdly, we investigate the relations between the expressive power of CRPQ, CCFPQ, and their generalizations. In several cases we show that replacing regular expressions by context-free grammars does increase expressive power. Finally, we look at including context-free grammars in more powerful logics than conjunctive queries. We do so by adding negation and provide expressivity relations between the obtained languages.

  13. FoIKS 2014.
    Implication and axiomatization of functional constraints on patterns with an application to the RDF data model. Jelle Hellings, Marc Gyssens, Jan Paredaens, and Yuqing Wu. (2014). In: Foundations of Information and Knowledge Systems, 250-269. Springer. DOI: 10.1007/978-3-319-04939-7_12. See also AMAI 2016.
    author copy, slides.
    Abstract

    Akhtar et al. introduced equality-generating constraints and functional constraints as an initial step towards dependency-like integrity constraints for RDF data. Here, we focus on functional constraints. The usefulness of functional constraints is not limited to the RDF data model. Therefore, we study the functional constraints in the more general setting of relations with arbitrary arity. We show that a chase algorithm for functional constraints can be normalized to a more specialized symmetry-preserving chase algorithm. This symmetry-preserving chase algorithm is subsequently used to construct a sound and complete axiomatization for the functional constraints. This axiomatization is in particular applicable in the RDF data model, solving a major open problem of Akhtar et al.

  14. ICDT 2013.
    Walk logic as a framework for path query languages on graph databases. Jelle Hellings, Bart Kuijpers, Jan Van den Bussche, and Xiaowang Zhang. (2013). In: Proceedings of the 16th International Conference on Database Theory, 117-128. ACM. DOI: 10.1145/2448496.2448512.
    author copy, slides.
    Abstract

    Motivated by the current interest in languages for expressing path queries to graph databases, this paper proposes to investigate Walk Logic (WL): the extension of first-order logic on finite graphs with the possibility to explicitly quantify over walks. WL can serve as a unifying framework for path query languages. To support this claim, WL is compared in expressive power with various established query languages for graphs, such as first-order logic extended with reachability; the monadic second-order logic of graphs; hybrid computation tree logic; and regular path queries. WL also serves as a framework to investigate the following natural questions: Is quantifying over walks more powerful than quantifying over paths (walks without repeating nodes) only? Is quantifying over infinite walks more powerful than quantifying over finite walks only? WL model checking is decidable, but determining the precise complexity remains an open problem.

  15. SIGMOD 2012.
    Efficient external-memory bisimulation on DAGs. Jelle Hellings, George H.L. Fletcher, and Herman Haverkort. (2012). In: Proceedings of the 2012 ACM SIGMOD International Conference on Management of Data, 553-564. ACM. DOI: 10.1145/2213836.2213899. See also DBDBD 2011, Master thesis.
    author copy, slides, project page.
    Abstract

    In this paper we introduce the first efficient external-memory algorithm to compute the bisimilarity equivalence classes of a directed acyclic graph (DAG). DAGs are commonly used to model data in a wide variety of practical applications, ranging from XML documents and data provenance models, to web taxonomies and scientific workflows. In the study of efficient reasoning over massive graphs, the notion of node bisimilarity plays a central role. For example, grouping together bisimilar nodes in an XML data set is the first step in many sophisticated approaches to building indexing data structures for efficient XPath query evaluation. To date, however, only internal-memory bisimulation algorithms have been investigated. As the size of real-world DAG data sets often exceeds available main memory, storage in external memory becomes necessary. Hence, there is a practical need for an efficient approach to computing bisimulation in external memory.

    Our general algorithm has a worst-case IO-complexity of O(Sort(|N| + |E|)), where |N| and |E| are the numbers of nodes and edges, resp., in the data graph and Sort(n) is the number of accesses to external memory needed to sort an input of size n. We also study specializations of this algorithm to common variations of bisimulation for tree-structured XML data sets. We empirically verify efficient performance of the algorithms on graphs and XML documents having billions of nodes and edges, and find that the algorithms can process such graphs efficiently even when very limited internal memory is available. The proposed algorithms are simple enough for practical implementation and use, and open the door for further study of external-memory bisimulation algorithms. To this end, the full open-source C++ implementation has been made freely available.

Tutorials, Demos, and Talks

  1. VLDB 2020 Tutorial.
    Building High Throughput Permissioned Blockchain Fabrics: Challenges and Opportunities. Suyash Gupta, Jelle Hellings, Sajjad Rahnama, and Mohammad Sadoghi. (2020). In: Proceedings of the VLDB Endowment, 13(12), 3441-3444. VLDB. DOI: 10.14778/3415478.3415565.
    author copy, slides, video of the entire tutorial.
    Video Presentation
    Abstract

    Since the introduction of Bitcoin--the first widespread application driven by blockchains--the interest in the design of blockchain-based applications has increased tremendously. At the core of these applications are consensus protocols that securely replicate client requests among all replicas, even if some replicas are Byzantine faulty. Unfortunately, these consensus protocols typically have low throughput, and this lack of performance is often cited as the reason for the slow wider adoption of blockchain technology. Consequently, many works focus on designing more efficient consensus protocols to increase throughput of consensus.

    We believe that this focus on consensus protocols only explains part of the story. To investigate this belief, we raise a simple question: Can a well-crafted system using a classical consensus protocol outperform systems using modern protocols? In this tutorial, we answer this question by diving deep into the design of blockchain systems. Further, we take an in-depth look at the theory behind consensus, which can help users select the protocol that best-fits their requirements. Finally, we share our vision of high-throughput blockchain systems that operate at large scales.

  2. VLDB 2020 Demo.
    Scalable, resilient, and configurable permissioned blockchain fabric. Sajjad Rahnama, Suyash Gupta, Thamir M. Qadah, Jelle Hellings, and Mohammad Sadoghi. (2020). In: Proceedings of the VLDB Endowment, 13(12), 2893-2896. VLDB. DOI: 10.14778/3415478.3415502.
    author copy, video by Sajjad Rahnama.
    Abstract

    With the advent of Bitcoin, the interest of the database community in blockchain systems has steadily grown. Many existing blockchain applications use blockchains as a platform for monetary transactions, however. We deviate from this philosophy and present ResilientDB, which can serve in a suite of non-monetary data-processing blockchain applications. Our ResilientDB uses state-of-the-art technologies and includes a novel visualization that helps in monitoring the state of the blockchain application.

  3. DEBS 2020 Tutorial.
    Blockchain consensus unraveled: Virtues and limitations. Suyash Gupta, Jelle Hellings, Sajjad Rahnama, and Mohammad Sadoghi. (2020). In: Proceedings of the 14th ACM International Conference on Distributed and Event-Based Systems, 218-221. ACM. DOI: 10.1145/3401025.3404099.
    author copy, slides, video.
    Abstract

    Since the introduction of Bitcoin--the first wide-spread application driven by blockchains--the interest of the public and private sector in blockchains has skyrocketed. At the core of this interest are the ways in which blockchains can be used to improve data management, e.g., by enabling federated data management via decentralization, resilience against failure and malicious actors via replication and consensus, and strong data provenance via a secured immutable ledger.

    In practice, high-performance blockchains for data management are usually built in permissioned environments in which the participants are vetted and can be identified. In this setting, blockchains are typically powered by Byzantine fault-tolerant consensus protocols. These consensus protocols are used to provide full replication among all honest blockchain participants by enforcing an unique order of processing incoming requests among the participants.

    In this tutorial, we take an in-depth look at Byzantine fault-tolerant consensus. First, we take a look at the theory behind replicated computing and consensus. Then, we delve into how common consensus protocols operate. Finally, we take a look at current developments and briefly look at our vision moving forward.

  4. Reimagine 2020.
    An in-depth look of BFT consensus in blockchain: Challenges and opportunities. Suyash Gupta, Jelle Hellings, Sajjad Rahnama, and Mohammad Sadoghi. (2020).
    slides.
  5. FAB 2020.
    ResilientDB: Global scale resilient blockchain fabric. Suyash Gupta, Sajjad Rahnama, Jelle Hellings and Mohammad Sadoghi. (2020). In: The third International Symposium on Foundations and Applications of Blockchain.
    abstract, video by Suyash Gupta.
    Abstract

    Recent developments in blockchain technology have inspired innovative new designs in resilient distributed and database systems. At their core, these blockchain applications typically use Byzantine fault-tolerant consensus protocols to maintain a common state across all replicas, even if some replicas are faulty or malicious. Unfortunately, existing consensus protocols are not designed to deal with geo-scale deployments in which many replicas spread across a geographically large area participate in consensus.

    To address this, we present the Geo-Scale Byzantine Fault-Tolerant consensus protocol (GeoBFT). GeoBFT is designed for excellent scalability by using a topological-aware grouping of replicas in local clusters, by introducing parallelization of consensus at the local level, and by minimizing communication between clusters. To validate our vision of high-performance geo-scale resilient distributed systems, we implement GeoBFT in our efficient ResilientDB permissioned blockchain fabric. We show that GeoBFT is not only sound and provides great scalability, but also outperforms state-of-the-art consensus protocols by a factor of six in geo-scale deployments.

  6. Middleware 2019.
    An in-depth look of BFT consensus in blockchain: Challenges and opportunities. Suyash Gupta, Jelle Hellings, Sajjad Rahnama, and Mohammad Sadoghi. (2019). In: Proceedings of the 20th International Middleware Conference--Tutorials, 6-10. ACM. DOI: 10.1145/3366625.3369437.
    author copy, slides.
    Abstract

    Since the introduction of Bitcoin--the first wide-spread application driven by blockchains--the interest of the public and private sector in blockchains has skyrocketed. At the core of this interest are the ways in which blockchains can be used to improve data management, e.g., by enabling federated data management via decentralization, resilience against failure and malicious actors via replication and consensus, and strong data provenance via a secured immutable ledger.

    In practice, high-performance blockchains for data management are usually built in permissioned environments in which the participants are vetted and can be identified. In this setting, blockchains are typically powered by Byzantine fault-tolerant consensus protocols. These consensus protocols are used to provide full replication among all honest blockchain participants by enforcing an unique order of processing incoming requests among the participants.

    In this tutorial, we take an in-depth look at Byzantine fault-tolerant consensus. First, we take a look at the theory behind replicated computing and consensus. Then, we delve into how common consensus protocols operate. Finally, we take a look at current developments and briefly look at our vision moving forward.

  7. HPTS 2019.
    Efficient transaction processing in Byzantine fault tolerant environments. Suyash Gupta, Jelle Hellings, Thamir Qadah, Sajjad Rahnama, and Mohammad Sadoghi. (2019). In: 18th International Workshop on High Performance Transaction Systems.
    abstract, video by Suyash Gupta.
  8. DBDBD 2016.
    Graph query optimization using semi-join rewritings. Jelle Hellings. (2016). In: The Dutch-Belgian DataBase Day. See also CJ 2020, DBPL 2017, PhD thesis.
    abstract, slides.
  9. WOG 2013.
    Path querying on graph databases. Jelle Hellings. (2013). In: WOG (Wetenschappelijke Onderzoeksgemeenschap/Scientific Research Network) Meeting.
    long abstract, short abstract, slides.
  10. DBDBD 2011.
    Efficient external-memory bisimulation on DAGs. Jelle Hellings. (2011). In: The Dutch-Belgian DataBase Day. See also SIGMOD 2012, Master thesis.
    abstract, slides, project page.

PhD thesis and Master thesis

  1. PhD thesis.
    On tarski's relation algebra: Querying trees and chains and the semi-join algebra. Jelle Hellings. (2018). Hasselt University and transnational University of Limburg. Adviser: Marc Gyssens. See also CJ 2020, IS 2020, FoIKS 2018a, DBPL 2017, DBDBD 2016, DBPL 2015.
    author copy, thesis, slides, project page.
    Abstract

    Many practical query languages for graph data are based on fragments of Tarski's relation algebra which, optionally, is augmented with the Kleene-star operator. Examples include XPath, SPARQL, the RPQs, and GXPath. Because of this central role of (fragments of) the relation algebra, we study two aspects in more detail. Combined, these two studies give a detailed picture of the expressive power of the fragments of the relation algebra. Moreover, our results provide several opportunities for the development of new techniques for the efficient evaluation of graph queries.

  2. Master thesis.
    Bisimulation partitioning and partition maintenance. Jelle Hellings. (2011). Eindhoven University of Technology. Adviser: George H. L. Fletcher. See also SIGMOD 2012, DBDBD 2011.
    author copy, thesis, final slides, mid-term slides, poster, project page.
    Abstract

    The combination of graphs and node bisimulation is widely used within and outside of computer science. One example of this combination is constructing indices for speeding up queries on XML documents. Thereby XML documents can be represented by trees and many index types for indexing XML documents utilize the notion of bisimulation. Thereby the notion of bisimulation is used to relate nodes that have equivalent behavior with respect to queries performed on the XML documents. By replacing these bisimilar nodes one can reduce the size of the XML document and as such speed up queries. The objective of this thesis is to develop techniques for constructing and maintaining bisimulation partitions. Thereby a bisimulation partition groups nodes based on bisimilarity. In this thesis we primarily focus on very large directed acyclic graphs. The results in this thesis can for example be used to index very large XML documents.