Recursive Queries over Semantically Enriched Data Repositories

The complexity of information systems has increased remarkably in the last years, and more powerful tools to manage and access data are needed in a wide range of application areas. In particular, using ontologies to describe complex conceptual schemata of possibly heterogeneous and distributed data sources, and to access the data in them, is a topic of very active research. Most efforts to achieve this goal have resorted to data-base inspired query languages to access the data and Description Logics (DLs) as standard languages for describing ontologies. Specifically, tailored lightweight DLs have been developed, like the DL-Lite and the EL families, that are expressive enough for describing many application domains and at the same time support efficient query answering over data sources. However, the query languages considered so far lack recursion, a fundamental feature that is highly desirable in many applications. Recursion is necessary to express queries as natural as `is a reachable from b?`. Most data on the Web is found in semi-structured data sources (such as HTML or XML documents), and the basic access mechanisms for this kind of data are queries that use recursion to flexibly navigate and select nodes of information. Using (limited forms of) recursion, flexible and powerful query languages such as XPath have been developed and successfully deployed. Bridging the gap between the different kinds of data on the web and using ontologies to provide uniform access to heterogeneous sources will not be possible as long as we do not have suitable query languages that can flexibly navigate semi-structured data and that can be efficiently evaluated over DL ontologies. Recursive queries had not been explored in DLs, partly due to some negative results dating over a decade ago, that showed that popular families of recursive queries are undecidable already over very weak DLs. However, it was recently shown that some queries that allow a limited use of recursion, but which are still expressive enough to allow XPath-like data access, are decidable even over very expressive DLs. The complexity of answering these queries over lightweight DLs remains unexplored. Furthermore, this opens the encouraging perspective of possibly powerful and still unexplored decidable families of recursive queries over lightweight DL ontologies, that have the potential to dramatically improve the currently available data access technologies. This project aims at identifying such families, developing algorithms for them, and investigating their computational complexity.

This project was about bringing navigational queries with recursion to the realm of Ontology-based Data Access (OBDA). Recent years have seen enormous progress in the development of ontologies, which are sharable, machine-readable domain conceptualizations. A multitude of efforts in academia and industry have resulted in high-quality ontologies that faithfully capture expert knowledge from all kinds of domains. These ontologies offer many opportunities and are already making modern information systems smarter. In particular, in the paradigm of Ontology-based Data Access (OBDA), data sources are linked to a domain ontology. The ontology then provides the users a high-level conceptual view of the data, which may itself be incomplete and heterogeneous. The users can use the vocabulary and high-level view provided by the ontology to query the data. Crucially, in OBDA, users can retrieve not only the facts specifically stored in the (possibly incomplete) data, but also potentially implicit consequences implied by the data and the domain knowledge, obtaining more complete answers to queries. Both the theoretical foundations of OBDA, and the existing systems for its use in practice have progressed dramatically in the last decade. The main goal of this project was to extend the OBDA paradigm beyond the simple query languages considered before, which were limited mostly to conjunctive queries (that is, the well-known class of select-project-join relational algebra queries). In particular, in this project we studied queries that allow some form of recursion to express natural notions like "being reachable", and that support the kind of navigation that is needed for querying data on the Web and other forms of graph-shaped data that does not comply to a concrete schema. The main aim was to enable more flexible OBDA by means of queries with recursion, like regular path queries (RPQs) and their extensions. We obtained many decidability and complexity results, considering different combinations of query languages that support recursion, different families of ontology languages, and query reasoning services. We also developed reasoning techniques that may pave the way to practicable algorithms, with focus on translations that allow to reuse existing database technologies.