National Technical University of Athens (NTUA)
Optimizing query answering over expressive ontological knowledge
Abstract
dc:descriptionQuery answering over ontologies, i.e., the computation of answers to user queriesbased not only on explicitly stated information but also on implicit knowledge is animportant task in the context of the Semantic Web. In this direction, the SPARQLquery language has recently been extended by the World Wide Web Consortium(W3C) with so-called entailment regimes. An entailment regime defines how queriesare evaluated under more expressive semantics than SPARQL’s standard simpleentailment, 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 SPARQLOWLqueries are very expressive since variables can occur within complex conceptsand can also bind to concept or role names apart from individuals. Initially, wepresent a cost-based query planning strategy for SPARQL queries issued over anOWL ontology. The costs of the model are based on information about the instancesof concepts and roles that are extracted from a model abstraction built byan OWL reasoner. A static and a dynamic algorithm are presented which use thesecosts 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 clusteringapproach that allows for computing the cost functions based on one individualsample per cluster. Afterwards, we propose optimizations that target particularlythe complex queries that are allowed in SPARQL-OWL. These optimizations exploitquery 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 areavailable. This changes, however, when the statistics are less accurate, e.g., dueto non-deterministic reasoning decisions. For complex SPARQL-OWL queries weobserve an improvement of up to three orders of magnitude due to the proposedoptimizations. Finally, we show that the implemented system works well in a realworld application about cultural heritage data.
Degree
thesis:*- Grantor dc:publisher
- National Technical University of Athens (NTUA)
- Year dc:date
- 2014
Author and committee
dc:creator, dc:contributor.*- Authors dc:creator
-
- Kollia, Ilianna
- Κόλλια, Ηλιάννα
Subjects
dc:subject × 16- SPARQL απάντηση ερωτημάτων
- Σύστημα συνεπαγωγής OWL 2 άμεσης σημασιολογίας
- Βελτιστοποίηση ερωτημάτων
- SPARQL query answering
- SPARQL-owl
- OWL direct semantics entailment regime
- Query planning
- Query optimization
- Φυσικές Επιστήμες
- Επιστήμη Ηλεκτρονικών Υπολογιστών και Πληροφορική
- Επιστήμες Μηχανικού και Τεχνολογία
- Επιστήμη Ηλεκτρολόγου Μηχανικού, Ηλεκτρονικού Μηχανικού, Μηχανικού Η/Υ
- Natural Sciences
- Computer and Information Sciences
- Engineering and Technology
- Electrical Engineering, Electronic Engineering, Information Engineering
Rights
- Language dc:language
- eng
Identifiers
dc:identifier.*- Identifier
- 10.12681/eadd/39509