Efficient data management and data access have become a primary problem in the design and development of applications, especially due to the large amount of data we produce every day. Description logics (DLs) are a logic-based formalism for knowledge representation (KR) and reasoning that can be used to effectively model a certain domain of interest in a structured and well-defined way. In the realm of data access, conjunctive query (CQ) answering is one of the primary reasoning tasks over knowledge bases (KBs) for many applications.
Conjunctive Query Answering over Unrestricted OWL 2 Ontologies [PhD Project]
Challenges
When considering expressive description logics (DLs), query answering can be computationally very expensive, even when considering only complexity w.r.t. the size of the data (data complexity). Reasoners for CQ answering, although heavily optimized, often sacrifice expressive power of the input ontology or completeness of the computed answers in order to achieve tractability and scalability for the problem.
Approach
We designed and developed a hybrid query answering architecture that combines black-box services to provide a CQ answering service for OWL (Web Ontology Language). Specifically, it combines scalable CQ answering services for tractable languages with a CQ answering service for a more expressive language approaching the full OWL 2. If the query can be fully answered by one of the tractable services, then that service is used. Otherwise, the tractable services are used to compute lower and upper bound approximations, taking the union of the lower bounds and the intersection of the upper bounds. If the bounds do not coincide, then the “gap” answers are checked using the “full” service.
These techniques led to the development of two new systems:
- RSAComb, an efficient implementation of a new tractable answering service for the RSA (role safety acyclic) ontology language.
- ACQuA, a reference implementation of the proposed hybrid architecture combining RSAComb, PAGOdA, and HermiT to provide a CQ answering service for OWL.
Results
Our extensive evaluation shows how the additional computational cost introduced by reasoning over a more expressive language like RSA can still provide a significant improvement compared to relying on a fully-fledged reasoner. Additionally, we showed how ACQuA can reliably match PAGOdA’s performance and further limit its performance issues, especially when the latter extensively relies on the underlying fully-fledged reasoner.
Selected Publications:
- Federico Igne, Stefano Germano, and Ian Horrocks. “Computing CQ Lower-Bounds over OWL 2 Through Approximation to RSA”. In: The Semantic Web – ISWC 2021 – 20th International Semantic Web Conference, ISWC 2021. Vol. 12922. Lecture Notes in Computer Science. Springer, 2021, pp. 200–216.
- Federico Igne, Stefano Germano, and Ian Horrocks. “RSAComb: Combined Approach for CQ Answering in RSA”. In: Proceedings of the 34th International Workshop on Description Logics (DL 2021). Vol. 2954. CEUR Workshop Proceedings. CEUR-WS.org, 2021.
- Federico Igne, Stefano Germano, and Ian Horrocks. “Conjunctive query answering over unrestricted OWL 2 ontologies”. In: Semantic Web. [currently under review]
Team
Federico Igne [PhD Candidate], Ian Horrocks [Supervisor], Stefano Germano [Supervisor]
Partners
Acknowledgements
This work was supported by the SIRIUS Centre for Scalable Data Access (Research Council of Norway, project 237889).