Ontology-mediated Queries for Graph Databases

Modern software applications need to manage and access increasingly complex data, which often does not conform to rigid schemas used in traditional databases. Graph databases and Description Logics (DLs) provide complementary tools for managing such loosely-structured information. For example, an ontology written in a DL can be used to capture knowledge about a given application domain in a machine readable format. This knowledge can then be used for answering ontology-mediated queries (OMQs): a user query is evaluated not directly over the available data, but a reasoning engine is employed to incorporate the knowledge in the ontology, possibly inferring facts that are not explicitly present in the data. OMQs and queries over graph databases have many similarities, but they also have major differences that we aim to reconcile in this project. In particular, when answering OMQs one makes the so-called open-world assumption (information is assumed to be incomplete), while the closed-world assumption is made in graph databases (information completeness is assumed). It is acknowledged however that both assumptions are too strong, and that the users should have the ability to specify which part of the data is to be assumed as complete and which as incomplete. Second, OMQs do not support navigational features that are very common in languages for querying graph databases and other representations of loosely- structured data (e.g., the path expressions in the XPath query language for XML documents, or the property paths in the SPARQL query language for RDF data). In this project, we will consider extensions of standard OMQs with features that overcome the above two drawbacks, i.e. we will study OMQs that allow to mix the open-world and the closed-world assumptions, and that simultaneously support navigational features. For such rich OMQs, we will study the following fundamental database-theoretic properties: - The first major goal is to compare the expressive power of the considered OMQs with the expressive power of classic database query languages. To this end, we will mainly develop translations from OMQs into suitable variations of Datalog. This will also enable us to transfer existing results from the setting of Datalog to the setting of OMQs, e.g., to reuse existing efficient Datalog engines for answering OMQs. - The second major goal is to study the computational complexity of reasoning tasks to support the design of OMQs. In particular, we will investigate the query containment and the query emptiness problems for the OMQs introduced in the project. These static analysis problems lie at the core of query design and optimization techniques.

Modern software applications need to manage and access increasingly complex data, which often does not conform to rigid schemas used in traditional databases. Description Logics and Graph Databases provide useful but complementary tools for managing such loosely-structured information. Most of the results of this project were on obtaining new data management and access methods that enjoy the positive features stemming from these two different areas. For instance, Description Logics enable the so-called ontology-mediated queries (OMQs), where domain knowledge expressed as an ontology can be used to enable automated reasoning, which in turn can be used for enhanced access to (possibly incomplete) data. In contrast, Graph Databases use query languages that are usually more expressive than the ones used in Description Logics, usually featuring some form of recursion. In addition to the differences in expressiveness, the two areas make different assumptions about data; inheriting the positive features of the two areas requires reconciliation of those different assumptions. For instance, when answering OMQs one makes the so-called open-world assumption (information is assumed to be incomplete), while the closed-world assumption is made in graph databases (information completeness is assumed). This project provided significant contributions to the logical foundations of managing and querying graph-structured data with the help of Description Logics, thus helping to bridge the gap between Description Logics and Graph Databases. Our main results can be summarized as follows: - We developed a collection of translations from OMQs into suitable variations of Datalog, which is a classic query language in Database Theory. The existence of such rewritings was not known prior to our work, which showed that classical query languages can succinctly express the more recent and seemingly more powerful (ontology-mediated) query languages. - We have introduced new logic-based formalisms for data management (Resilient Logic Programs, Clopen Knowledge Bases, Triguarded Fragment), and we have studied their semantic and computational properties. - We have introduced new ways to query graph-structured data. For instance, we introduced a framework for OMQs that have conditional query answers, which allows for a more powerful and flexible formulation of user queries. Another example is the introduced framework and foundational results for an interactive exploration of data via ontology-mediated queries. - We have studied the theoretical foundations of the W3C SHACL standard, which is a new standard that will help maintain the quality of graph-structured data on the Web. We have proposed a new interpretation (called "semantics") for recursive SHACL integrity constraints, which fills in some important gaps in the original SHACL standard. We believe our work is likely to influence the future revisions of this standard by W3C.