Please use this identifier to cite or link to this item:
Title: Optimizing Query Answering Over Expressive Ontological Knowledge
Authors: Ηλιάννα Κόλλια
Σταφυλοπάτης Ανδρέας-Γεώργιος
Keywords: sparql query answering
owl direct semantics entailment regime
query planning
query optimization
Issue Date: 11-Jul-2014
Abstract: Query answering over ontologies, i.e., the computation of answers to user queries based not only on explicitly stated information but also on implicit knowledge is an important task in the context of the Semantic Web. In this direction, the SPARQL query language has recently been extended by the World Wide Web Consortium (W3C) with so-called entailment regimes. An entailment regime defines how queries are evaluated under more expressive semantics than SPARQL's standard simple entailment, which is based on subgraph matching.In this thesis we describe a sound and complete algorithm for the OWL DirectSemantics entailment regime of SPARQL (SPARQL-OWL). The proposed SPARQL-OWL queries are very expressive since variables can occur within complex concepts and can also bind to concept or role names apart from individuals. Initially, we present a cost-based query planning strategy for SPARQL queries issued over an OWL ontology. The costs of the model are based on information about the instances of concepts and roles that are extracted from a model abstraction built by an OWL reasoner. A static and a dynamic algorithm are presented which use these costs to find optimal or near optimal execution orders for the templates of a query. For the dynamic case, we improve the performance by exploiting an individual clustering approach that allows for computing the cost functions based on one individual sample per cluster. Afterwards, we propose optimizations that target particularly the complex queries that are allowed in SPARQL-OWL. These optimizations exploit query rewriting techniques and the concept and role hierarchies to efficiently answersuch queries.The proposed algorithm and optimizations have been implemented in a systemcalled OWL-BGP. Our experimental study, using this system, shows that thestatic ordering usually outperforms the dynamic one when accurate statistics are available. This changes, however, when the statistics are less accurate, e.g., due to non-deterministic reasoning decisions. For complex SPARQL-OWL queries we observe an improvement of up to three orders of magnitude due to the proposed optimizations. Finally, we show that the implemented system works well in a real world application about cultural heritage data.
Appears in Collections:Διδακτορικές Διατριβές - Ph.D. Theses

Files in This Item:
File SizeFormat 
PD2014-0033.pdf1.28 MBAdobe PDFView/Open

Items in Artemis are protected by copyright, with all rights reserved, unless otherwise indicated.