Showing 1–16 of 16 results for author: Hidders, J

Common Foundations for Recursive Shape Languages

Authors: Shqiponja Ahmetaj, Iovka Boneva, Jan Hidders, Maxime Jakubowski, Jose-Emilio Labra-Gayo, Wim Martens, Fabio Mogavero, Filip Murlak, Cem Okulmus, Ognjen Savković, Mantas Šimkus, Dominik Tomaszuk

Abstract: As schema languages for RDF data become more mature, we are seeing efforts to extend them with recursive semantics, applying diverse ideas from logic programming and description logics. While ShEx has an official recursive semantics based on greatest fixpoints (GFP), the discussion for SHACL is ongoing and seems to be converging towards least fixpoints (LFP). A practical study we perform shows tha… ▽ More As schema languages for RDF data become more mature, we are seeing efforts to extend them with recursive semantics, applying diverse ideas from logic programming and description logics. While ShEx has an official recursive semantics based on greatest fixpoints (GFP), the discussion for SHACL is ongoing and seems to be converging towards least fixpoints (LFP). A practical study we perform shows that, indeed, ShEx validators implement GFP, whereas SHACL validators are more heterogeneous. This situation creates tension between ShEx and SHACL, as their semantic commitments appear to diverge, potentially undermining interoperability and predictability. We aim to clarify this design space by comparing the main semantic options in a principled yet accessible way, hoping to engage both theoreticians and practitioners, especially those involved in developing tools and standards. We present a unifying formal semantics that treats LFP, GFP, and supported model semantics (SMS), clarifying their relationships and highlighting a duality between LFP and GFP on stratified fragments. Next, we investigate to which extent the directions taken by SHACL and ShEx are compatible. We show that, although ShEx and SHACL seem to be going in different directions, they include large fragments with identical expressive power. Moreover, there is a strong correspondence between these fragments through the aforementioned principle of duality. Finally, we present a complete picture of the data and combined complexity of ShEx and SHACL validation under LFP, GFP, and SMS, showing that SMS comes at a higher computational cost under standard complexity-theoretic assumptions. △ Less

Submitted 13 May, 2026; v1 submitted 22 April, 2026; originally announced April 2026.

On the generic information capacity of relational schemas with a single binary relation

Authors: Benoît Groz, Jan Hidders, Nina Pardal, Jan Van den Bussche, Piotr Wieczorek

Abstract: We consider database schemas consisting of a single binary relation, with key constraints and inclusion dependencies. Over this space of 20 schemas, we completely characterize when one schema is generically dominated by another schema. Generic dominance, a classical notion for measuring information capacity, expresses that every instance of a schema can be uniquely represented in the dominating sc… ▽ More We consider database schemas consisting of a single binary relation, with key constraints and inclusion dependencies. Over this space of 20 schemas, we completely characterize when one schema is generically dominated by another schema. Generic dominance, a classical notion for measuring information capacity, expresses that every instance of a schema can be uniquely represented in the dominating schema, through application of a deterministic, generic data transformation. Our investigation is motivated both by current interest in schema design for graph databases, as well as by intrinsic scientific interest. We also consider the ternary case, but without inclusion dependencies, and discuss how the notions change in the presence of object identifiers. △ Less

Submitted 18 March, 2026; originally announced March 2026.

MSC Class: 68P15

The KG-ER Conceptual Schema Language

Authors: Enrico Franconi, Benoît Groz, Jan Hidders, Nina Pardal, Sławek Staworko, Jan Van den Bussche, Piotr Wieczorek

Abstract: We propose KG-ER, a conceptual schema language for knowledge graphs that describes the structure of knowledge graphs independently of their representation (relational databases, property graphs, RDF) while helping to capture the semantics of the information stored in a knowledge graph. We propose KG-ER, a conceptual schema language for knowledge graphs that describes the structure of knowledge graphs independently of their representation (relational databases, property graphs, RDF) while helping to capture the semantics of the information stored in a knowledge graph. △ Less

Submitted 11 June, 2026; v1 submitted 4 August, 2025; originally announced August 2025.

Comments: Published in Proceedings of IRIS-AI (https://iris-ai.org)

MSC Class: 68P15

Common Foundations for SHACL, ShEx, and PG-Schema

Authors: S. Ahmetaj, I. Boneva, J. Hidders, K. Hose, M. Jakubowski, J. E. Labra-Gayo, W. Martens, F. Mogavero, F. Murlak, C. Okulmus, A. Polleres, O. Savkovic, M. Simkus, D. Tomaszuk

Abstract: Graphs have emerged as an important foundation for a variety of applications, including capturing and reasoning over factual knowledge, semantic data integration, social networks, and providing factual knowledge for machine learning algorithms. To formalise certain properties of the data and to ensure data quality, there is a need to describe the schema of such graphs. Because of the breadth of ap… ▽ More Graphs have emerged as an important foundation for a variety of applications, including capturing and reasoning over factual knowledge, semantic data integration, social networks, and providing factual knowledge for machine learning algorithms. To formalise certain properties of the data and to ensure data quality, there is a need to describe the schema of such graphs. Because of the breadth of applications and availability of different data models, such as RDF and property graphs, both the Semantic Web and the database community have independently developed graph schema languages: SHACL, ShEx, and PG-Schema. Each language has its unique approach to defining constraints and validating graph data, leaving potential users in the dark about their commonalities and differences. In this paper, we provide formal, concise definitions of the core components of each of these schema languages. We employ a uniform framework to facilitate a comprehensive comparison between the languages and identify a common set of functionalities, shedding light on both overlapping and distinctive features of the three languages. △ Less

Submitted 3 February, 2025; originally announced February 2025.

Comments: To be published at WWW 2025

ACM Class: I.2.4

The Linked Data Benchmark Council (LDBC): Driving competition and collaboration in the graph data management space

Authors: Gábor Szárnyas, Brad Bebee, Altan Birler, Alin Deutsch, George Fletcher, Henry A. Gabb, Denise Gosnell, Alastair Green, Zhihui Guo, Keith W. Hare, Jan Hidders, Alexandru Iosup, Atanas Kiryakov, Tomas Kovatchev, Xinsheng Li, Leonid Libkin, Heng Lin, Xiaojian Luo, Arnau Prat-Pérez, David Püroja, Shipeng Qi, Oskar van Rest, Benjamin A. Steer, Dávid Szakállas, Bing Tong , et al. (8 additional authors not shown)

Abstract: Graph data management is instrumental for several use cases such as recommendation, root cause analysis, financial fraud detection, and enterprise knowledge representation. Efficiently supporting these use cases yields a number of unique requirements, including the need for a concise query language and graph-aware query optimization techniques. The goal of the Linked Data Benchmark Council (LDBC)… ▽ More Graph data management is instrumental for several use cases such as recommendation, root cause analysis, financial fraud detection, and enterprise knowledge representation. Efficiently supporting these use cases yields a number of unique requirements, including the need for a concise query language and graph-aware query optimization techniques. The goal of the Linked Data Benchmark Council (LDBC) is to design a set of standard benchmarks that capture representative categories of graph data management problems, making the performance of systems comparable and facilitating competition among vendors. LDBC also conducts research on graph schemas and graph query languages. This paper introduces the LDBC organization and its work over the last decade. △ Less

Submitted 30 August, 2024; v1 submitted 10 July, 2023; originally announced July 2023.

ACM Class: H.2.4

Static Analysis of Graph Database Transformations

Authors: Iovka Boneva, Benoit Groz, Jan Hidders, Filip Murlak, Slawomir Staworko

Abstract: We investigate graph transformations, defined using Datalog-like rules based on acyclic conjunctive two-way regular path queries (acyclic C2RPQs), and we study two fundamental static analysis problems: type checking and equivalence of transformations in the presence of graph schemas. Additionally, we investigate the problem of target schema elicitation, which aims to construct a schema that closel… ▽ More We investigate graph transformations, defined using Datalog-like rules based on acyclic conjunctive two-way regular path queries (acyclic C2RPQs), and we study two fundamental static analysis problems: type checking and equivalence of transformations in the presence of graph schemas. Additionally, we investigate the problem of target schema elicitation, which aims to construct a schema that closely captures all outputs of a transformation over graphs conforming to the input schema. We show all these problems are in EXPTIME by reducing them to C2RPQ containment modulo schema; we also provide matching lower bounds. We use cycle reversing to reduce query containment to the problem of unrestricted (finite or infinite) satisfiability of C2RPQs modulo a theory expressed in a description logic. △ Less

Submitted 20 April, 2023; v1 submitted 11 April, 2023; originally announced April 2023.

Journal ref: Symposium on Principles of Database Systems, Jun 2023, Seattle, United States

PG-Schema: Schemas for Property Graphs

Authors: Renzo Angles, Angela Bonifati, Stefania Dumbrava, George Fletcher, Alastair Green, Jan Hidders, Bei Li, Leonid Libkin, Victor Marsault, Wim Martens, Filip Murlak, Stefan Plantikow, Ognjen Savković, Michael Schmidt, Juan Sequeda, Sławek Staworko, Dominik Tomaszuk, Hannes Voigt, Domagoj Vrgoč, Mingxi Wu, Dušan Živković

Abstract: Property graphs have reached a high level of maturity, witnessed by multiple robust graph database systems as well as the ongoing ISO standardization effort aiming at creating a new standard Graph Query Language (GQL). Yet, despite documented demand, schema support is limited both in existing systems and in the first version of the GQL Standard. It is anticipated that the second version of the GQL… ▽ More Property graphs have reached a high level of maturity, witnessed by multiple robust graph database systems as well as the ongoing ISO standardization effort aiming at creating a new standard Graph Query Language (GQL). Yet, despite documented demand, schema support is limited both in existing systems and in the first version of the GQL Standard. It is anticipated that the second version of the GQL Standard will include a rich DDL. Aiming to inspire the development of GQL and enhance the capabilities of graph database systems, we propose PG-Schema, a simple yet powerful formalism for specifying property graph schemas. It features PG-Types with flexible type definitions supporting multi-inheritance, as well as expressive constraints based on the recently proposed PG-Keys formalism. We provide the formal syntax and semantics of PG-Schema, which meet principled design requirements grounded in contemporary property graph management scenarios, and offer a detailed comparison of its features with those of existing schema languages and graph database systems. △ Less

Submitted 8 July, 2023; v1 submitted 20 November, 2022; originally announced November 2022.

Comments: 26 pages

Journal ref: Proc. ACM Manag. Data (2023)

Expressiveness within Sequence Datalog

Authors: Heba Aamer, Jan Hidders, Jan Paredaens, Jan Van den Bussche

Abstract: Motivated by old and new applications, we investigate Datalog as a language for sequence databases. We reconsider classical features of Datalog programs, such as negation, recursion, intermediate predicates, and relations of higher arities. We also consider new features that are useful for sequences, notably, equations between path expressions, and "packing". Our goal is to clarify the relative ex… ▽ More Motivated by old and new applications, we investigate Datalog as a language for sequence databases. We reconsider classical features of Datalog programs, such as negation, recursion, intermediate predicates, and relations of higher arities. We also consider new features that are useful for sequences, notably, equations between path expressions, and "packing". Our goal is to clarify the relative expressiveness of all these different features, in the context of sequences. Towards our goal, we establish a number of redundancy and primitivity results, showing that certain features can, or cannot, be expressed in terms of other features. These results paint a complete picture of the expressiveness relationships among all possible Sequence Datalog fragments that can be formed using the six features that we consider. △ Less

Submitted 14 June, 2022; originally announced June 2022.

Comments: This paper is the extended version of a paper presented at PODS 2021

Threshold Queries in Theory and in the Wild

Authors: Angela Bonifati, Stefania Dumbrava, George Fletcher, Jan Hidders, Matthias Hofer, Wim Martens, Filip Murlak, Joshua Shinavier, Sławek Staworko, Dominik Tomaszuk

Abstract: Threshold queries are an important class of queries that only require computing or counting answers up to a specified threshold value. To the best of our knowledge, threshold queries have been largely disregarded in the research literature, which is surprising considering how common they are in practice. In this paper, we present a deep theoretical analysis of threshold query evaluation and show t… ▽ More Threshold queries are an important class of queries that only require computing or counting answers up to a specified threshold value. To the best of our knowledge, threshold queries have been largely disregarded in the research literature, which is surprising considering how common they are in practice. In this paper, we present a deep theoretical analysis of threshold query evaluation and show that thresholds can be used to significantly improve the asymptotic bounds of state-of-the-art query evaluation algorithms. We also empirically show that threshold queries are significant in practice. In surprising contrast to conventional wisdom, we found important scenarios in real-world data sets in which users are interested in computing the results of queries up to a certain threshold, independent of a ranking function that orders the query results by importance. △ Less

Submitted 17 November, 2021; v1 submitted 29 June, 2021; originally announced June 2021.

The Future is Big Graphs! A Community View on Graph Processing Systems

Authors: Sherif Sakr, Angela Bonifati, Hannes Voigt, Alexandru Iosup, Khaled Ammar, Renzo Angles, Walid Aref, Marcelo Arenas, Maciej Besta, Peter A. Boncz, Khuzaima Daudjee, Emanuele Della Valle, Stefania Dumbrava, Olaf Hartig, Bernhard Haslhofer, Tim Hegeman, Jan Hidders, Katja Hose, Adriana Iamnitchi, Vasiliki Kalavri, Hugo Kapp, Wim Martens, M. Tamer Özsu, Eric Peukert, Stefan Plantikow , et al. (16 additional authors not shown)

Abstract: Graphs are by nature unifying abstractions that can leverage interconnectedness to represent, explore, predict, and explain real- and digital-world phenomena. Although real users and consumers of graph instances and graph workloads understand these abstractions, future problems will require new abstractions and systems. What needs to happen in the next decade for big graph processing to continue t… ▽ More Graphs are by nature unifying abstractions that can leverage interconnectedness to represent, explore, predict, and explain real- and digital-world phenomena. Although real users and consumers of graph instances and graph workloads understand these abstractions, future problems will require new abstractions and systems. What needs to happen in the next decade for big graph processing to continue to succeed? △ Less

Submitted 11 December, 2020; originally announced December 2020.

Comments: 12 pages, 3 figures, collaboration between the large-scale systems and data management communities, work started at the Dagstuhl Seminar 19491 on Big Graph Processing Systems, to be published in the Communications of the ACM

ACM Class: C.3; E.0; H.2; J.0

J-Logic: a Logic for Querying JSON

Authors: Jan Hidders, Jan Paredaens, Jan Van den Bussche

Abstract: We propose a logical framework, based on Datalog, to study the foundations of querying JSON data. The main feature of our approach, which we call J-Logic, is the emphasis on paths. Paths are sequences of keys and are used to access the tree structure of nested JSON objects. J-Logic also features ``packing'' as a means to generate a new key from a path or subpath. J-Logic with recursion is computat… ▽ More We propose a logical framework, based on Datalog, to study the foundations of querying JSON data. The main feature of our approach, which we call J-Logic, is the emphasis on paths. Paths are sequences of keys and are used to access the tree structure of nested JSON objects. J-Logic also features ``packing'' as a means to generate a new key from a path or subpath. J-Logic with recursion is computationally complete, but many queries can be expressed without recursion, such as deep equality. We give a necessary condition for queries to be expressible without recursion. Most of our results focus on the deterministic nature of JSON objects as partial functions from keys to values. Predicates defined by J-Logic programs may not properly describe objects, however. Nevertheless we show that every object-to-object transformation in J-Logic can be defined using only objects in intermediate results. Moreover we show that it is decidable whether a positive, nonrecursive J-Logic program always returns an object when given objects as inputs. Regarding packing, we show that packing is unnecessary if the output does not require new keys. Finally, we show the decidability of query containment for positive, nonrecursive J-Logic programs. △ Less

Submitted 7 June, 2020; originally announced June 2020.

Finding AND-OR Hierarchies in Workflow Nets

Authors: Jacek Sroka, Jan Hidders

Abstract: This paper presents the notion of AND-OR reduction, which reduces a WF net to a smaller net by iteratively contracting certain well-formed subnets into single nodes until no more such contractions are possible. This reduction can reveal the hierarchical structure of a WF net, and since it preserves certain semantical properties such as soundness, it can help with analysing and understanding why a… ▽ More This paper presents the notion of AND-OR reduction, which reduces a WF net to a smaller net by iteratively contracting certain well-formed subnets into single nodes until no more such contractions are possible. This reduction can reveal the hierarchical structure of a WF net, and since it preserves certain semantical properties such as soundness, it can help with analysing and understanding why a WF net is sound or not. The reduction can also be used to verify if a WF net is an AND-OR net. This class of WF nets was introduced in earlier work, and arguably describes nets that follow good hierarchical design principles. It is shown that the AND-OR reduction is confluent up to isomorphism, which means that despite the inherent non-determinism that comes from the choice of subnets that are contracted, the final result of the reduction is always the same up to the choice of the identity of the nodes. Based on this result, a polynomial-time algorithm is presented that computes this unique result of the AND-OR reduction. Finally, it is shown how this algorithm can be used to verify if a WF net is an AND-OR net. △ Less

Submitted 6 January, 2017; originally announced January 2017.

External memory bisimulation reduction of big graphs

Authors: Yongming Luo, George H. L. Fletcher, Jan Hidders, Yuqing Wu, Paul De Bra

Abstract: In this paper, we present, to our knowledge, the first known I/O efficient solutions for computing the k-bisimulation partition of a massive directed graph, and performing maintenance of such a partition upon updates to the underlying graph. Ubiquitous in the theory and application of graph data, bisimulation is a robust notion of node equivalence which intuitively groups together nodes in a graph… ▽ More In this paper, we present, to our knowledge, the first known I/O efficient solutions for computing the k-bisimulation partition of a massive directed graph, and performing maintenance of such a partition upon updates to the underlying graph. Ubiquitous in the theory and application of graph data, bisimulation is a robust notion of node equivalence which intuitively groups together nodes in a graph which share fundamental structural features. k-bisimulation is the standard variant of bisimulation where the topological features of nodes are only considered within a local neighborhood of radius $k\geqslant 0$. The I/O cost of our partition construction algorithm is bounded by $O(k\cdot \mathit{sort}(|\et|) + k\cdot scan(|\nt|) + \mathit{sort}(|\nt|))$, while our maintenance algorithms are bounded by $O(k\cdot \mathit{sort}(|\et|) + k\cdot \mathit{sort}(|\nt|))$. The space complexity bounds are $O(|\nt|+|\et|)$ and $O(k\cdot|\nt|+k\cdot|\et|)$, resp. Here, $|\et|$ and $|\nt|$ are the number of disk pages occupied by the input graph's edge set and node set, resp., and $\mathit{sort}(n)$ and $\mathit{scan}(n)$ are the cost of sorting and scanning, resp., a file occupying $n$ pages in external memory. Empirical analysis on a variety of massive real-world and synthetic graph datasets shows that our algorithms perform efficiently in practice, scaling gracefully as graphs grow in size. △ Less

Submitted 2 May, 2013; v1 submitted 2 October, 2012; originally announced October 2012.

Comments: 17 pages

On Generating *-Sound Nets with Substitution

Authors: Jacek Sroka, Jan Hidders

Abstract: We present a method for hierarchically generating sound workflow nets by substitution of nets with multiple inputs and outputs. We show that this method is correct and generalizes the class of nets generated by other hierarchical approaches. The method involves a new notion of soundness which is preserved by the generalized type of substitution that is presented in this paper. We show that this no… ▽ More We present a method for hierarchically generating sound workflow nets by substitution of nets with multiple inputs and outputs. We show that this method is correct and generalizes the class of nets generated by other hierarchical approaches. The method involves a new notion of soundness which is preserved by the generalized type of substitution that is presented in this paper. We show that this notion is better suited than *-soundness for use with the presented type of generalized substitution, since {*}-soundness is not preserved by it. It is moreover shown that it is in some sense the optimal notion of soundness for the purpose of generating sound nets by the presented type of substitution. △ Less

Submitted 1 October, 2013; v1 submitted 13 August, 2012; originally announced August 2012.

SERIMI - Resource Description Similarity, RDF Instance Matching and Interlinking

Authors: Samur Araujo, Jan Hidders, Daniel Schwabe, Arjen P. de Vries

Abstract: The interlinking of datasets published in the Linked Data Cloud is a challenging problem and a key factor for the success of the Semantic Web. Manual rule-based methods are the most effective solution for the problem, but they require skilled human data publishers going through a laborious, error prone and time-consuming process for manually describing rules mapping instances between two datasets.… ▽ More The interlinking of datasets published in the Linked Data Cloud is a challenging problem and a key factor for the success of the Semantic Web. Manual rule-based methods are the most effective solution for the problem, but they require skilled human data publishers going through a laborious, error prone and time-consuming process for manually describing rules mapping instances between two datasets. Thus, an automatic approach for solving this problem is more than welcome. In this paper, we propose a novel interlinking method, SERIMI, for solving this problem automatically. SERIMI matches instances between a source and a target datasets, without prior knowledge of the data, domain or schema of these datasets. Experiments conducted with benchmark collections demonstrate that our approach considerably outperforms state-of-the-art automatic approaches for solving the interlinking problem on the Linked Data Cloud. △ Less

Submitted 6 July, 2011; originally announced July 2011.

Instance-Independent View Serializability for Semistructured Databases

Authors: Stijn Dekeyser, Jan Hidders, Jan Paredaens, Roel Vercammen

Abstract: Semistructured databases require tailor-made concurrency control mechanisms since traditional solutions for the relational model have been shown to be inadequate. Such mechanisms need to take full advantage of the hierarchical structure of semistructured data, for instance allowing concurrent updates of subtrees of, or even individual elements in, XML documents. We present an approach for concur… ▽ More Semistructured databases require tailor-made concurrency control mechanisms since traditional solutions for the relational model have been shown to be inadequate. Such mechanisms need to take full advantage of the hierarchical structure of semistructured data, for instance allowing concurrent updates of subtrees of, or even individual elements in, XML documents. We present an approach for concurrency control which is document-independent in the sense that two schedules of semistructured transactions are considered equivalent if they are equivalent on all possible documents. We prove that it is decidable in polynomial time whether two given schedules in this framework are equivalent. This also solves the view serializability for semistructured schedules polynomially in the size of the schedule and exponentially in the number of transactions. △ Less

Submitted 26 May, 2005; originally announced May 2005.

ACM Class: H.2