Foundations of Reasoning in the Shape Constraint Language

The Semantic Web is an initiative of the World Wide Web Consortium (W3C) that extends the World Wide Web by setting standards to organize Web data so that it can be processed by machines. As a first step towards this aim, W3C standardized in 2004 the Resource Description Framework (RDF) as the data model of the Web. RDF offers a flexible semi-structured format, by storing data as triples, easily representable as a graph, which makes it suitable for modeling information from Web resources. This has favored its wide adoption and large and growing RDF graphs are continuously being published on the Web. However, one often encounters RDF data that is incorrect. As ensuring data quality became increasingly important in RDF-based applications, the presence of faulty facts in RDF graphs has been widely acknowledged as a serious issue. To address this, W3C recommended in 2017 the Shapes Constraint Language (or SHACL), a machine-readable constraint language for describing and validating RDF graphs. Intuitively, it allows us to specify a set of conditions to be checked against an RDF graph, which can be exploited by applications to improve the quality of the graph. SHACL has already been adopted by existing tools and software packages and has been the focus of research works. However, being only a recent W3C standard, SHACL is not yet well-understood, and its theoretical foundations are not yet well-established. This project will develop solid theoretical foundations for SHACL, paving the way for powerful techniques for intelligent Web data management and reasoning about data quality, and significantly advancing the current state-of-the-art. We will investigate fundamental static analysis tasks aimed at supporting the design of SHACL constraints as well as the yet unexplored but crucial task of how to handle violations of SHACL constraints by RDF graphs. More precisely, the first major goal of the project is to investigate the satisfiability and containment of SHACL constraints, the most primitive static analysis problems that lie at the core of constraint design and optimization techniques. These tasks are crucial for building meaningful sets of SHACL constraints without inconsistencies, but also for optimization purposes. The second major goal is to formalize the notions of explanations and repairs for SHACL and study their properties. Roughly, this allows us to explain why some RDF graph violates the SHACL constraints and to provide ways to fix the graph so that it conforms with the constraints. This is a key point mentioned in the SHACL specification, under so-called validation reports. This study will also clarify the relationship between the emerging and the classic approaches to managing data inconsistency and explanations, e.g., it will allow us to transfer existing results from the setting of the closely related language OWL and that of databases to the setting of SHACL.

Data is becoming increasingly essential in our digital age. To be useful for people and applications, data needs to be correct and trustworthy. Yet the unprecedented diversity and volume of data available today make it prone to errors, missing information, and faulty facts. This is especially true when large-scale data from different sources is integrated, or when data is stored on the Web, where it is often incomplete or flawed and may lead to erroneous conclusions. Ensuring data quality is therefore a pressing challenge, especially in areas such as healthcare, banking, business, science, and public administration, where decisions based on correct data are crucial. This project addressed such challenges by developing theoretical foundations for automatically establishing and improving the quality of Web-like data represented as knowledge graphs. Knowledge graphs represent information as objects and relationships between them, for example people, organizations, or products and how they are connected. The project focused on SHACL, a standardized language for describing and validating constraints on knowledge graphs. Such constraints can express, for example, that every person should have exactly one birth date or that a publication should have at least one author. SHACL is already adopted by many tools and software systems, but when the project started, its theoretical foundations were still not sufficiently understood. This project contributed to advancing these foundations. A central contribution was the study of explanations and repairs for violations of SHACL constraints. Instead of only reporting that some data is invalid, the developed methods help identify the problematic parts of the data and analyze which changes could make the data valid again. This supports more transparent data quality management and helps users understand, explain, and improve complex datasets. In many applications, knowledge graphs change over time, often repeatedly and automatically. The project also studied whether a given update operation is guaranteed to preserve the constraints for all possible input data that already satisfies them. This is useful because the same update pattern may be applied many times and to very large datasets; proving its safety once can reduce costly repeated validation and prevent errors before they enter the data. The project further studied how to obtain meaningful answers even in the presence of imperfect data, by considering possible repairs and using the information that remains reliable. It also investigated efficient validation methods for complex SHACL constraints, helping avoid unnecessary computation in large knowledge graphs. Finally, the project clarified how SHACL relates to Wikidata constraints, ontologies, Description Logics, and related graph schema languages such as ShEx and PG Schema, thereby connecting different communities and technologies for structured data. Overall, the project contributes to more trustworthy digital data and supports future tools for automatically checking, explaining, and improving data quality.