Database techniques for ontology-based data access

Abstract

Ontology-based Data Acess (OBDA) is a method for linking an ontology, which encodes knowledge about the classes and properties of entities for a given application domain,to underlying data sources. These data sources, managed by specialized systems, can be in various forms and usually reside in pre-existing repositories. The linking is accomplished through declarative mappings, which are used to generate ontology terms from information in the data sources. Instead of materializing all the ontology terms, the user of the relevant application can pose a query over the ontology, and then a process of query transformation is carried out, which has as a result a query in the native language of the underlying data sources. This resulted query is then executed, and the results are presented to the user, transformed as ontology terms. This approach, also known as virtual knowledge graph approach, has the advantage that provides the user with a familiar vocabulary over which he can pose a query, concealing details about the underlying data sources, such as complex schemas and storage particularities. On the other hand, the process of transforming the initial query over the ontology into a query over the under lyingsources, leads in many cases to complex and large queries. In this thesis, we study the problem of efficient query answering for OBDA systems from a database perspective, concentrating on the ontology language OWL 2 QL, which is a dialect of the OWL family specifically tailored for the case where massive data are stored in an external data source. We are also concentrating on the case where the initial query posed over the ontology is in the form of a union of conjunctive queries. As expected,this issue heavily depends on the exact kind of the underlying data source. For this reason we make a distinction between three different commonly encountered scenarios. In the first scenario we consider that the underlying system is a single relational database management system. In the second scenario we consider that we have a federation of different relational systems. Finally, in the third scenario we consider the case where data are stored in a specialized triple store in the form of RDF statements.For the first scenario, we identify redundant processing as a key problem in OBDA query execution over a relational system. Examples of such processing are duplicate answers obtained during query evaluation, which must finally be discarded, or common expressions evaluated multiple times from different parts of the same complex query. Many optimizations that aim to minimize this problem have been proposed and implemented,mostly based on semantic query optimization techniques, by exploiting ontological axioms and constraints defined in the database schema. However, operations that introduce re-dundant processing are still generated in many practical settings, and this is a factor that impacts query execution. To handle this issue, we propose a cost-based method for query translation, which starts from an initial default translation and uses information about redundant processing in order to come up with an equivalent, more efficient translation. The method operates in a number of steps, by relying on certain heuristics indicating that we obtain a more efficient query in each step. Through experimental evaluation using the Ontop system for ontology-based data access, we exhibit the benefits of our method. For the second scenario we have developed a system that acts as a mediator betweenthe OBDA system and the federated databases. This system, built using the Exareme engine, decomoses the produced query into different fragments, sends these fragments for evaluation in the external databases and imports the intermediate results that correspond to these fragments. Finally, these intermediate results are combined in order to produce the final query result. During this process, we have adapted techniques and methods from database literature for usage in the context of OBDA. These methods cover areas such as data integration, common subexpression identification, caching of intermediate query results and distributed processing. The developed mediator system has been integrated into the platform of the Optique research project and has been successfully deployed in a demanding real world use case, federating seven different databases which contain geological data. For the last scenario, we have developed PARJ, a specialized in-memory RDF store which takes into consideration ontological hierarchies during join processing with very low performance overhead, using on-the-fly computation of the inferences regarding class and property hierarchies. In the spirit of the OBDA approach, PARJ avoids expensive preprocessing and materialization of implications. PARJ is also amenable to straight forward parallelization. Specifically, we present a join implementation that allows to achieve any desired degree of parallelism on arbitrary join queries and RDF graphs stored in memory using compact vertical partitioning. We use an adaptive join processing approach,such that we take advantage of complete or even partial ordering of RDF data, which is compactly stored in order to increase spatial locality and keep memory consumption low,coupled with an ID-to-Position vector index used when ordering does not allow for efficient scanning of the input relation. Finally, we experimentally show the efficiency and scalability of our proposal.

Στην επιστημονική περιοχή της Αναπαράστασης Γνώσης και Συλλογιστικής, οι οντολογίες διαδραματίζουν καθοριστικό ρόλο στη μοντελοποίηση γνώσης για έναν τομέα εφαρμογών. Μια οντολογία κωδικοποιεί πληροφορίες σχετικά με τις κατηγορίες αντικειμένων του τομέα και τις σχέσεις μεταξύ τους, παρέχοντας στους χρήστες της εφαρμογής με μια οικεία μοντελοποίηση του τομέα. Επιπλέον, αξιώματα εκφρασμένα σε λογική και κωδικοποιημένα στην οντολογία, μπορούν να χρησιμοποιηθούν για την απόκτηση νέας γνώσης μέσω συμπερασμού. Η Κοινοπραξία του παγκόσμιου ιστού (World Wide WebConsortium-W3C) συνιστά τη χρήση της γλώσσας οντολογιών OWL, ως την οικογένεια γλωσσών για αναπαράσταση γνώσης στον παγκόσμιο ιστό. Η ανάκτηση δεδομένων βάσει οντολογιών (Ontology-based Data Access-ΟBDA) είναι μια μέθοδος διασύνδεσης οντολογιών με υποκείμενες εξωτερικές πηγές δεδομένων μέσω δηλωτικών αντιστοιχίσεων (mappings). Οι συγκεκριμένες αντιστοιχίσεις μπορούν να θεωρηθούν ως κανόνες που δημιουργούν αντικείμενα της οντολογίας βάσει επερωτήσεων στα εξωτερικά δεδομένα. Στη συνέχεια, ένας χρήστης μπορεί να θέσει μια επερώτηση στην οντολογία και αυτή η επερώτηση μπορεί να μεταφραστεί στη γλώσσα επερωτήσεων του υποκείμενου συστήματος διαχείρισης δεδομένων, ή αλλιώς της εξωτερικής πηγής δεδομένων, χρησιμοποιώντας τις αντιστοιχίσεις και αποστέλλεται για εκτέλεση, παρέχοντας στο χρήστη τα επιθυμητά αποτελέσματα, σαν τα δεδομένα να αποτελούσαν εξαρχής μέρος της οντολογίας. Παρά το ότι από άποψη πολυπλοκότητας υπάρχουν αποτελεσματικοί αλγόριθμοι για απάντηση επερωτήσεων σε συστήματα που πραγματοποιούν ανάκτηση δεδομένων βάσει οντολογιών (ΟBDA-συστήματα), το τελικό ερώτημα που προκύπτει και που πρέπει να εκτελεστεί στις εξωτερικές βάσεις δεδομένων είναι σε πολλές πρακτικές περιπτώσεις πολύπλοκο και μεγάλο. Για παράδειγμα, δεν είναι ασυνήθιστο σε ένα τυπικό OBDA σενάριο, σε περίπτωση που στην οντολογία ορίζονται μεγάλες ιεραρχίες κλάσεων και ιδιοτήτων, μια αρχική συζευκτική επερώτηση πάνω στην οντολογία να μεταφραστεί σε μια ένωση συζευκτικών επερωτήσεων, που μπορεί να περιέχει εκατοντάδες ή χιλιάδες υποερωτήματα. Η παρούσα διδακτορική διατριβή προσφέρει τεχνικές για την αντιμετώπιση του προαναφερθέντος ζητήματος από την πλευρά των βάσεων δεδομένων. Συγκεκριμένα, επικεντρωνόμαστε στην διάλεκτο OWL 2 QL της οικογένειας γλωσσών για οντολογίες OWL, η οποία διάλεκτος είναι ειδικά προσαρμοσμένη για την περίπτωση μεταγραφής επερωτήσεων όταν έχουμε μαζικά δεδομένα σε εξωτερικές πηγές. Σε σχέση με τις αντιστοιχίσεις ανάμεσα στην οντολογία και τις εξωτερικές πηγές, επικεντρωνόμαστε στην γλώσσα αντιστοιχήσεων R2RML, η οποία αποτελεί επίσημη σύσταση του W3C, ή άλλες γλώσσες παρόμοιας εκφραστικότητας. Σε αυτό το πλαίσιο, κάνουμε μια διάκριση μεταξύ τριών διαφορετικών σεναρίων OBDA, ανάλογα με το είδος του υποκείμενου συστήματος διαχείρισης δεδομένων, και υλοποιούμε αποδοτικές τεχνικές για κάθε ένα από τρία αυτά σενάρια. Συγκεκριμένα, κατά το πρώτο σενάριο θεωρούμε ότι τα δεδομένα αποθηκεύονται σε μια εξωτερική σχεσιακή βάση δεδομένων με αυθαίρετο σχεσιακό σχήμα. Κατά το δεύτερο σενάριο τα δεδομένα αποθηκεύονται σε πολλές εξωτερικές βάσεις δεδομένων, όπου η καθεμία έχει το δικό της σχήμα και μπορεί να βρίσκεται σε διαφορετική τοποθεσία. Τέλος, στο τρίτο σενάριο τα υποκείμενα δεδομένα βρίσκονται υπό την μορφή γράφου, ακολουθώντας το μοντέλο RDF, και είναι αποθηκευμένα σε ένα εξειδικευμένο σύστημα διαχείρισης αυτού του είδους των δεδομένων. Το RDF είναι ένα μοντέλο δεδομένων ευρέως χρησιμοποιούμενο για την ενσωμάτωση δεδομένων από διαφορετικές πηγές,ακολουθώντας ένα απλό σχήμα γράφου κατά το οποίο τα δεδομένα μοντελοποιούνται ως τριπλέτες που έχουν τη μορφή υποκείμενο-κατηγόρημα-αντικείμενο. Σε κάθε ένα από αυτά τα σενάρια προτείνονται λύσεις και αναπτύσσονται συστήματα τα οποία βελτιώνουν τους χρόνους εκτέλεσης επερωτήσεων, ενώ η συνεισφορά της παρούσας διατριβής επιβεβαιώνεται εμπειρικά με την διεξαγωγή εκτεταμένων πειραμάτων.