Optimizing query answering over expressive ontological knowledge

Abstract

Query 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.

Στη διατριβή αυτή έχουν αναπτυχθεί τεχνικές βελτιστοποίησης για την απάντηση συζευκτικών ερωτημάτων που τίθενται σεβάσεις γνώσης περιγραφικής λογικής. Με βάση το σύστημα συνεπαγωγής άμεσης σημασιολογίας OWL της SPARQLδημιουργήθηκε μια γλώσσα συζευκτικών ερωτημάτων, η οποία επιτρέπει τη χρήση μεταβλητών στη θέση εννοιών και ρόλωνεκτός από τη θέση στιγμιοτύπων, και αναπτύχθηκε ένας αλγόριθμος απάντησης ερωτημάτων στη γλώσσα αυτή.Στη συνέχεια αναπτύχθηκε μια τεχνική για την εύρεση μιας όσο το δυνατόν πιο αποδοτικής σειράς εκτέλεσης των ατόμωνενός (συζευκτικού) ερωτήματος. Σύμφωνα με την τεχνική αυτή τα άτομα ενός ερωτήματος ταξινομούνται με βάση το κόστοςεκτέλεσής τους. Ο υπολογισμός του κόστους ενός ατόμου στηρίζεται σε πληροφορία σχετική με τα στιγμιότυπα των εννοιώνκαι ρόλων της υπό εξέταση οντολογίας η οποία εξάγεται από ένα αρχικό μοντέλο που κατασκευάζεται από μια OWL μηχανήσυλλογιστικής. Παρουσιάζεται ένας στατικός και ένας δυναμικός αλγόριθμος ταξινόμησης που χρησιμοποιούν αυτά τα κόστηγια να βρουν βέλτιστες ή σχεδόν βέλτιστες σειρές εκτέλεσης των ατόμων των ερωτημάτων. Στην περίπτωση του δυναμικούαλγορίθμου, χρησιμοποιείται μια τεχνική συσταδοποίησης στιγμιοτύπων και υπολογίζονται οι συναρτήσεις κόστους με βάσητο πολύ ένα στιγμιότυπο από καθεμιά από τις συστάδες. Στη συνέχεια προτείνονται τεχνικές επανεγγραφής ερωτημάτων καιαναλύεται πως μπορούν να χρησιμοποιηθούν ειδικές λειτουργίες των OWL μηχανών συλλογιστικής και η ιεραρχία εννοιώνκαι ρόλων της υπό εξέταση οντολογίας για τη μείωση του χρόνου απάντησης ερωτημάτων. Οι τεχνικές αυτές είναι ιδιαίτεραχρήσιμες για την αξιολόγηση ατόμων ερωτημάτων που περιέχουν μεταβλητές στη θέση εννοιών και ρόλων.Η αποτελεσματικότητα των προτεινόμενων τεχνικών αξιολογείται χρησιμοποιώντας πρότυπα σύνολα ελέγχου. Από τηνπειραματική αυτή μελέτη προκύπτει ότι ο στατικός αλγόριθμος ταξινόμησης συνήθως υπερτερεί του δυναμικού ότανχρησιμοποιείται για ερωτήματα για τα οποία έχουμε ακριβείς πληροφορίες/στατιστικές από την αρχή. Για ερωτήματα πουτίθενται σε μη ντετερμινιστικές οντολογίες (οντολογίες με διαζευκτική πληροφορία) και περιέχουν πολλά άτομα για τα οποίαδεν είναι δυνατή η εξαγωγή ακριβών στατιστικών εκ των προτέρων, ο δυναμικός αλγόριθμος είναι πιο αποδοτικός. Η χρήσητεχνικών συσταδοποίησης οδηγεί σε βελτίωση της απόδοσης για ερωτήματα με μεγάλο πλήθος αποτελεσμάτων. Για τέτοιασύνθετα ερωτήματα οι τεχνικές αυτές μπορούν να οδηγήσουν σε βελτίωση μέχρι και τρεις τάξεις μεγέθους. Στο τέλοςακολουθεί μια περιγραφή του τρόπου που μπορούν να χρησιμοποιηθούν οι προτεινόμενες τεχνικές και το αναπτυγμένοσύστημα σε μια πραγματική εφαρμογή σημασιολογικής αναζήτησης πολιτιστικών αντικειμένων.