TL;DR
This paper introduces a novel approach to querying object-relational knowledge bases using SQL, bridging the gap between familiar relational database technology and ontology-based data access (OBDA). By leveraging the description logic CFDInc, the authors show how to efficiently compute query answers without needing to translate data into triple-based formats, making OBDA more accessible to those familiar with SQL.
What Problem Does This Paper Address?
Ontology-based data access (OBDA) aims to provide a unified way to query data sources using background knowledge captured in ontologies. A major challenge is scalability, especially when dealing with large datasets. Many existing OBDA approaches rely on translating queries into SQL for relational databases, but this often requires complex mappings and can be inefficient. The authors address the need for a method that directly leverages existing relational database technology and SQL for querying object-relational schemata within an OBDA context, without the overhead of triple-based representations. They specifically target the problem of making OBDA accessible to users already proficient in SQL.
Methods
The core of the paper's contribution lies in developing efficient algorithms for query answering over CFDInc knowledge bases. CFDInc is a description logic designed to naturally represent relational and object-relational schemata. The approach combines two key techniques:
- ABox Completion: An algorithm is presented to complete the ABox (assertions about individuals) of a CFDInc knowledge base. This completion is designed to be efficient, with PTIME data complexity, and serves as a basis for checking knowledge base consistency.
- Query Rewriting: A novel query rewriting technique transforms a given conjunctive query (CQ) into a union of CQs. This rewritten query can then be evaluated as a SQL query over the completed ABox, viewed as a relational database. This process avoids the need for explicit object invention, a common bottleneck in other approaches.
The authors also discuss how standard relational database schemas can be naturally captured as CFDInc TBoxes, eliminating the need for additional mappings.
Datasets
The paper uses the UNIV schema as a running example throughout the text to illustrate concepts. For experimental evaluation, they used a modified version of the LUBM benchmark, introducing a relational schema and then defining virtual ABoxes based on configurations of generated data.
Key Insights and Ideas
- Bridging SQL and OBDA: The most significant insight is demonstrating how to make OBDA directly accessible to SQL-literate users by leveraging CFDInc's ability to represent object-relational schemata. This bypasses the need for complex triple-based transformations.
- Efficient ABox Completion: The development of a PTIME-complexity ABox completion procedure is crucial for practical scalability.
- Query Rewriting without Object Invention: The paper's query rewriting technique cleverly avoids the need for creating new anonymous individuals (object invention), which is a known performance bottleneck in other OBDA systems.
- Natural Schema Representation: CFDInc's suitability for directly encoding relational schemas simplifies the integration of existing databases into an OBDA framework.
- Trade-off between Rewriting and Completion: The authors highlight that while their approach aims for efficiency, the potential exponential blow-up in query rewriting cannot be avoided in general, as the combined complexity for CQ answering in CFDInc is PSPACE-complete. However, they show how concept hierarchies can be handled efficiently through data completion.
Key Results
- PTIME Data Complexity for CQ Answering: The proposed approach achieves PTIME data complexity for conjunctive query answering over CFDInc knowledge bases.
- Efficient Algorithms: The paper presents efficient algorithms for ABox completion and query rewriting.
- Experimental Validation: Experiments on a modified LUBM benchmark showed that the ABox completion process was comparable to raw data loading, and queries completed within a few seconds, even on large instances, demonstrating the practical feasibility of the approach.
Limitations and Future Work
- Potential Exponential Blow-up: The authors acknowledge that the query rewriting step can lead to an exponential blow-up in general, as the combined complexity for CQ answering in CFDInc is PSPACE-complete. However, they show that this blow-up originating from concept hierarchies can be mitigated by data completion.
- Future Work: The paper suggests two main avenues for future research:
- Incremental ABox Completion: Developing techniques for incremental ABox completion to further improve efficiency.
- Relaxing Concept Compatibility Restrictions: Exploring ways to relax restrictions on concept compatibility based on underlying table primary keys, potentially using techniques based on referring expressions.
Summary updated