Shapes in Graph Data: Theory and Implementation

Defining shapes for the validation of RDF graphs is a non-trivial endeavour. While in most cases the shapes are manually defined, various methods were proposed for the extraction of shapes. In this talk, we went through the methods for extracting shapes and discussed open challenges related to the integration of shapes extracted from different sources.

Shapes are typically mined from RDF graphs [1, 2, 3, 4], and thus, their effectiveness is inherently influenced by the size and complexity of the RDF graph. However, these systems often overlook the constraints imposed by individual artifacts which contributed to the construction of RDF graphs.

RDF graphs are often constructed by applying ontology terms to heterogeneous data according to a set of mapping rules. Methods were proposed to extract SHACL shapes from the data schema [6, 7], the ontology [5] or the mapping rules [8]. However, these approaches lead to limited or incomplete constraints.

Methods were also proposed that exploit all artifacts associated with the construction of RDF graphs. SCOOP extract shapes from data schemas, ontologies, and mapping rules, and integrates the shapes extracted from each artifact into a unified shapes graph. SCOOP’s implementation was configured to extract shapes from XML Schema [9] using XSD2SHACL [6], OWL Ontologies [10] using Astrea [5], and RML mapping rules [11] using RML2SHACL [8].

SCOOP was applied to real-world use cases and experimental results. So far methods that exploit all artifacts associated with the construction of RDF outperform methods that extract shapes from RDF graphs. However, the integration of shapes often leads to inconsistences. Such inconsistences were discussed during the talk as well as strategies to deal with them.

Property graphs are becoming pervasive in various graph processing applications using interconnected data. They allow encoding multi-labeled nodes and edges, as well as their properties, represented as key/value pairs. Although property graphs are widely used in several open-source and commercial graph databases, their schema definition is not as well-understood as that of their relational counterparts. The property graph schema discovery problem consists of extracting the underlying schema concepts and types from such graph datasets. The talk provides an overview of two recent schema discovery methods for property graphs.

The first method, MRSchema [1], builds upon Cypher queries to extract the node and edge serialization of a property graph, then leverages a MapReduce type inference system to obtain subtype and supertype information for nodes, and analyzes these to compute node hierarchies. The second method, GMMSchema [2], relies on hierarchical clustering using a Gaussian Mixture Model, which accounts for both node labels and properties, unlike MRSchema. This allows for preventing the discovery of spurious types and achieving efficient performance without accuracy loss. Moreover, the approach supports efficient incremental schema maintenance, as showcased in the corresponding DiscoPG tool [3].

DiscoPG allows users to perform schema discovery for both static and dynamic graph datasets. Suitable visualization layouts and dedicated dashboards enable the user perception of the static and dynamic inferred schema on the node clusters, as well as the differences in runtimes and clustering quality. To our knowledge, DiscoPG is the first system to tackle the property graph schema discovery problem. As such, it supports the insightful exploration of the graph schema components and their evolving behavior, while revealing the underpinnings of the clustering-based discovery process.

In this talk, I delve into the crucial role of constraints in maintaining data integrity in knowledge graphs with a specific focus on Wikidata, one of the most extensive collaboratively maintained open data knowledge graphs on the Web. The World Wide Web Consortium (W3C) recommends SHACL as the constraint language for validating Knowledge Graphs, which comes in two different levels of expressivity, SHACL-Core, as well as SHACL-SPARQL. Despite the availability of SHACL, Wikidata currently represents its property constraints through its own RDF data model, which relies on Wikidata’s specific reification mechanism. This talk discusses whether and how the semantics of Wikidata property constraints, can be formalized using SHACL-Core, SHACL-SPARQL, as well as directly as SPARQL queries.

We give an introduction to PG-Keys, which together with PG-Schemas forms a community consensus proposal for property graph schema standards. PG-Keys enable the definition of key constraints on property graphs under different modes, which are combinations of basic restrictions that require the key to be exclusive, mandatory, and singleton. Further, PG-Keys can be defined on nodes, edges, and properties since in practice these all can represent valid entities. PG-Keys was an outcome of the Linked Data Benchmark Council’s Property Graph Schema Working Group, consisting of members from industry, academia, and ISO GQL standards group, representing the past, present, and future of the science and practice of property graph data management.

Shapes, may they be formulated in SHACL or ShEx, have become an important instrument for validating knowledge graphs and ensuring that their content adheres to a set of well-defined constraints. Building upon such constraints, downstream applications incl. machine learning can benefit from the ensured or increased quality of knowledge graphs. Despite their usefulness in a broad range of situations, the adoption of shapes is hampered by the fact that there so far is a lack of tools that enable efficient mining of meaningful shapes. This motivated us to develop an approach that can automatically mine shapes from very large knowledge graphs [2] while providing an effective means to identify meaningful shapes based on support and confidence. As an extension, we have developed SHACTOR [1], which offers users a graphical interface and the opportunity to directly edit and update the underlying knowledge graph based on violations and inconsistencies identified after mining the shapes. While the current approach focuses on a subset of SHACL, we are working on extending the scope by enabling ShEx and a broader range of constraints.

Using SHACL, we present the notion of neighborhood of a node $v$ satisfying a given shape in a graph $G$. This neighborhood is a subgraph of $G$, and provides data provenance of $v$ for the given shape. We establish a correctness property for the obtained provenance mechanism, by proving that neighborhoods adhere to the Sufficiency requirement articulated for provenance semantics for database queries. As an additional benefit, neighborhoods allow a novel use of shapes: the extraction of a subgraph from an RDF graph, the so-called shape fragment. We compare shape fragments with SPARQL queries. We discuss implementation strategies for computing neighborhoods, and present initial experiments demonstrating that our ideas are feasible.

The Shapes Constraint Language (SHACL) is a W3C recommendation language used for validating RDF data by examining specific shapes within graphs. While previous research has largely focused on validation, the standard decision problems of satisfiability and containment have only been investigated for simplified versions of SHACL. In this talk, we offer a view of SHACL’s diverse features and introduce Shape Constraint Logic (SCL), an extension of a first-order language that accurately captures SHACL’s semantics. Additionally, we present MSCL, a second-order extension of SCL, which allows us to define, in a unified formal logic framework, the main recursive semantics of SHACL. Using this framework, we provide a detailed analysis of (un)decidability and complexity for the satisfiability and containment decision problems across different SHACL fragments. Notably, while both problems are undecidable for the complete language, we identify decidable combinations of interesting features, even amidst recursion.

Shape Expressions (ShEx) is a concise and human-readable language to describe and validate RDF data. In this talk, we present an introduction to the ShEx language, describing the main features of the language and how it can be used for RDF validation. We started with a short motivation about the need of ShEx and we later presented the notion of shape in ShEx as well as the evolution of the language and its main motivation and features.

In this talk, we presented a comparison between ShEx (Shape Expressions) and SHACL (Shapes Constraint Language). Although they have several common features, there are several differences. An important one is the motivation for their design: while ShEx has more emphasis on Description and Validation, SHACL has more emphasis on Constraints and Validation which makes ShEx schemas more similar to a grammar that defines RDF data topologies, which SHACL shapes are more similar to a conjunction of constraints about RDF data.

In this talk, I present a learning algorithm for learning simple Shex expressions from typed graphs. These expressions do not include disjunction, counting, or negation. We demonstrate that while learning from a single typed graph is straightforward, the problem becomes more intricate for multi-typed graphs. This complexity arises partly due to the introduction of types. We isolate specific cases that lead to these difficulties and identify conditions under which the problem remains tractable (polynomial time) or becomes intractable.

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.

Graph databases are becoming widely successful as data models that allow to effectively represent and process complex relationships among various types of data. Data-graphs are particular types of graph databases whose representation allows both data values in the paths and in the nodes to be treated as first class citizens by the query language. As with any other type of data repository, data-graphs may suffer from errors and discrepancies with respect to the real-world data they intend to represent. In this work, we explore the notion of probabilistic unclean data-graphs, in order to capture the idea that the observed (unclean) data-graph is actually the noisy version of a clean one that correctly models the world but that we know only partially. As the factors that lead to such a state of affairs may be many, e.g., all different types of clerical errors or unintended transformations of the data, and depend heavily on the application domain, we assume an epistemic probabilistic model that describes the distribution over all possible ways in which the clean (uncertain) data-graph could have been polluted. Based on this model we define two computational problems: data cleaning and probabilistic query answering and study for both of them their corresponding complexity when considering that the polluting transformation of the data-graph can be caused by either removing (subset), adding (superset), or modifying (update) nodes and edges. For data cleaning, we explore restricted versions when the transformation only involves updating data-values on the nodes.

Since the introduction of the Semantic Web in the late 90s, schema and ontology languages to describe the schema of what we now call “Knowledge Graphs” have played a central role. The semantic basis of these ontology languages have – historically – been based on formalisms such as Frame Logic, Description Logics as well as Datalog. The syntactic representations of Schema axioms is integrated in Knowledge Graphs by representations of axioms in RDF, using the W3C standardised RDF, RDFS and OWL vocabularies. OWL and RDFS can therefore be both seen as logical languages, but also simply as RDF vocabularies, a constrained use of which allows us to “encode” terminological axioms as part of an RDF (knowledge) graph. Yet, an unconstrained use of these vocabularies yields obviously “unintuitive” graphs. In this short talk/paper we would like to discuss two questions, namely: (a) is there too much syntactic freedom in RDF and OWL? (b) (how) can useful syntactic fragments of OWL and RDFS usage be captured by constraints and shapes? In the course of (b) we also aim at providing an “historical” overview of (semantic and syntactic) OWL and RDFS fragments from the literature.

We define SHACL abstract syntax and propose two semantics for the recursive case, and show their differences. We identify four selected issues that reflect differences between PG-Schema and SHACL. In particular, we discuss: (1) differences in labels for SHACL shape expressions and PG-Schema labels; (2) the support for negation in expressions; (3) quantification over edges and cardinality constraints; and finally (4) differences in open and closed constraints for both formalisms.

W3C has recently introduced SHACL as a new standard for integrity constraints on RDF graphs. Unfortunately, the standard defines the semantics of non-recursive constraints only, which has spurred recent research efforts into finding a suitable, mathematically crisp semantics for constraints with cyclic dependencies. To this end, Corman et al. [4] introduced a semantics related to supported models known in logic programming, while Andreşel et al. [1] presented a semantics based on stable models known in Answer Set Programming (ASP). In [2], the authors argue that recursive SHACL can be naturally equipped with a semantics inspired in the well-founded semantics for recursive logic programs with default negation [2]. This semantics is not only intuitive, but it is also computationally tractable, unlike the previous proposals. In this talk and demo, we review the well-founded semantics of SHACL and present an implementation of a new validator for this semantics. The implementation combines multiple technologies in order to obtain good efficiency and coverage of the features of the SHACL standard. In particular, our ShaWell⁵⁵5https://github.com/cem-okulmus/shawell system uses a sophisticated strategy to issue a series of SPARQL queries over an RDF triple store, whose results are post-processed to obtain a validation outcome. For non-recursive SHACL constraints, this yields a system that is largely compliant to the SHACL standard. In case of recursion, ShaWell additionally employs a deductive database engine DLV to evaluate a logic program that is produced as part of the validation process. In this way, the SHACL validation task is reduced to the problem of evaluating an ordinary logic program under the well-founded semantics. This method is similar to the one in [3], where a SAT solver was used for handling the supported model semantics from [4].

The Wikidata community announced the debut of the schema namespace in 2019. Wikidata editors contribute schemas in the Shape Expressions language to the schema namespace. As of February 2024, editors have contributed more than four hundred schemas describing domains from the life sciences, to the humanities, to computing.

Wikidata editors use schemas to communicate data models and to validate entity data. Each schema page contains a link to the ShEx2 Simple Online Validator so that editors can identify which Wikidata items are currently in conformance with a schema and which items require changes in order to be brought into conformance. Each schema has a unique identifier and support for labels and descriptions in the human languages Wikidata accommodates.

Wikidata editors have written schemas leveraging many feature of ShEx including recursion and importing one schema into another.

As awareness of Wikidata’s schema namespace grows, we anticipate more editors will author schemas, more editors will develop ShEx-based tooling for the community, and that the ecosystem of schemas that anyone can reuse and edit will continue to thrive.

We give an introduction to the W3C-recommended Shapes Constraint Language, SHACL. We present the syntax based on description logics introduced by Corman et al., and extended to full core SHACL by Jakubowski. We point out that SHACL views an RDF graph as an edge-labeled graph. This is interesting, since a working group during the seminar proposed edge-labeled graphs (with types) as a “greatest common lower bound” for RDF and property graphs. We present a generalization of SHACL in terms of general inclusions among shapes. Under the natural semantics, and excluding closedness constraints, we remark that this generalization does not add expressive power compared to real SHACL where left-hand shapes must be targets of specific kinds only. We discuss expressiveness issues, and approaches to recursion. We touch briefly upon SHACL engines and systems research on the topic, and mention applications of shapes beyond validation.

ISO/IEC 39075:2024 – GQL defines “a database language for modeling structured data as a graph, and for storing, querying, and modifying that data in a graph database or other graph store”. GQL was published in April 2024. Part of GQL is the concept of a graph type. A graph type as a GQL-object type describing a graph in terms of restrictions on its labels, properties, nodes, edges, and topology. The purpose of a graph type is to constrain the set of nodes and edges that can be contained in a graph. The talk gave an introduction into GQL graph types, covering the basics of the concept, DDL operations on graph types, syntax and semantics as well as the advanced topics of key label sets and structural consistency.

Experience has shown us that relational database schemas are very versatile and can model a variety of data modeling approaches, including property graphs. Moreover, novel techniques in query processing, such as worst-case optimal joins, or Datalog query processing, indicate that a relational approach to graph database applications is viable.

In this working group, we discussed two questions:

1. 1.

   Can we show in a systematic manner how schemas for property graphs, as expressed in the proposals of PG-Schema and PG-Keys, can be represented relationally, obtaining highly decomposed (6NF) schemas with key constraints and inclusion constraints such as foreign keys?

2. 2.

   Can the intent of a graph database application be formalized in a suitable variant of EER (extended Entity-Relationship) diagrams?

The established semantics of EER diagrams is through a mapping to relational schemas with constraints. The group discussed various use cases of EER diagrams with additional constructs inspired by PG-Schema, such as multivalued or optional properties. By observing the relational schemas that are obtained for these use cases, one may form a rough picture of the classes of relational constraints needed to support various graph database applications. While we believe that primary and foreign keys are two classes of constraints that can be enforced very efficiently, we have carefully identified features of EER models that require more expressive constraints, which leaves as an important open question if they can also be efficiently enforced.

The group has found that there is a lack of consensus on the interpretation of EER diagrams, with multiple semantics proposed that differ on finer points that in the context of graph databases can have important ramifications. For instance, do relationships in EER diagrams allow for multiple links between the same pair of entity instances (multi-graphs)? Can we assume that all entities have object identifiers, thus assuming that all entities are subclasses of a single top superclass?

We pointed out that a good understanding of mappings from property graphs to EER, and from EER to relational, may yield as an added bonus, a method to visualize a class of relational database schemas as PG-Schema with PG-Keys, as well as a way to visualize PG-Schemas in the more familiar notation of EER diagrams. Members of the working group will continue to stay in touch with each other to further investigate this line of research.