Βελτιστοποιημένοι αλγόριθμοι επαναγραφής ερωτημάτων για εκφραστικές περιγραφικές λογικές

Abstract

An important approach to query answering over OWL ontologies is via rewritingthe input ontology and query into a new set of axioms that are expressed inlogics for which scalable query answering algorithms exist. This approach has beenstudied for many important fragments of OWL like OWL 2 QL, OWL 2 EL, as well as Horn-SHIQ and SHIQ. An important family of rewriting algorithms arethe resolution-based ones, mostly due to their ability to adapt to any ontologylanguage and the long years of research in resolution theorem-proving. However,this generality comes with performance prices.In the current work we revisit and refine the resolution approaches in orderto design efficient rewriting algorithms for many important fragments of OWL 2.The underlying idea of our algorithms is to apply a resolution-based strategy thattakes into account the specific structure of the axioms supported by each language. First, we present an algorithm for the language DL-Lite, which is strongly relatedto OWL 2 QL. Our calculus is restricted so that it avoids performing manyunnecessary inferences, one of the main problems of these algorithms. Subsequently, we extend our algorithm to the language ELHI which is strongly related to OWL 2 EL. This is a difficult task as ELHI is an expressive language, however, weshow that the calculus for DL-Lite requires relatively small extensions. Finally, weextend our calculus for the very expressive language Horn-SHIQ. By followingthe same approach as in the case of ELHI, our calculus takes into account thecomplex axioms interactions in order to restict the resolution rules application.We have implemented our algorithms and we have conducted an extensive experimental evaluation using many well-known large and complex OWL ontologies.This is the first evaluation of rewriting algorithms of this magnitude. In the case ofDL-Lite and ELHI ontologies our results show that our system is in many casesseveral orders of a magnitude faster than several sofisticated rewriting systems.Similarly, in the case of Horn-SHIQ ontologies, our system greatly outperformsthe only available rewriting system for Horn-SHIQ.

Μία σημαντική προσέγγιση για την απάντηση ερωτημάτων σε οντολογίες είναι ηεπαναγραφή της οντολογίας και του ερωτήματος σε φορμαλισμούς για τους οποίους έχουν αναπτυχθεί αλγόριθμοι απάντησης ερωτημάτων. Η προσέγγιση έχει μελετηθεί για διαφορετικά υποσύνολα της γλώσσας OWL, όπως είναι οι γλώσσες OWL 2 QL, OWL 2 EL, καθώς και οι Horn-SHIQ και SHIQ. Μία βασική οικογένεια αλγορίθμων επαναγραφής περιλαμβάνει εκείνους που βασίζονται στην επίλυση. Χαρακτηριστικό τους είναι η δυνατότητα γενίκευσης σε διαφορετικές γλώσσες οντολογίας, καθώς και η δυνατότητα αξιοποίησης των τεχνικών βελτιστοποίησης που έχουν προκύψει από την εκτενή και μακροχρόνια έρευνα στον κλάδο της θεωρίας αποδείξεων με βάση την επίλυση. Την ίδια στιγμή όμως, η ικανότητα γενίκευσης που προσφέρει η μέθοδος της επίλυσης, μπορεί έχει επιπτώσεις στην επίδοση των αλγορίθμων. Στην παρούσα διατριβή μελετάμε και βελτιστοποιούμε υπάρχουσες μεθόδους που εφαρμόζουν τεχνικές επίλυσης με σκοπό να σχεδιάσουμε αποδοτικούς αλγορίθμους επαναγραφής για σημαντικά υποσύνολα της OWL 2. Η βασική ιδέα των αλγορίθμων είναι να αναπτύσσουν μια στρατηγική εφαρμογής κανόνων που θα λαμβάνει υπόψη τα ιδιαίτερα χαρακτηριστικά της κάθε γλώσσας περιγραφικής λογικής. Αρχικά, παρουσιάζουμε έναν αλγόριθμο για τη γλώσσα DL-Lite που σχετίζεται άμεσα με την OWL 2 QL. Ο λογισμός μας αποφεύγει την εκτέλεση περιττών κανόνων συμπερασμού επιλύοντας έτσι, ένα από τα βασικά προβλήματα αντίστοιχων αλγορίθμων. Στη συνέχεια, επεκτείνουμε τον αλγόριθμο για τη γλώσσα ELHI που σχετίζεται με την OWL 2 EL. Παρά την υψηλότερη εκφραστικότητα της γλώσσας ELHI, δείχνουμε ότι απαιτούνται λίγες μόνο τροποποιήσεις στον αλγόριθμο για την DL-Lite. Τέλος, επεκτείνουμε περαιτέρω τον αλγόριθμο, ώστε να υποστηρίζει την υψηλής εκφραστικότητας γλώσσα Horn-SHIQ. Ακολουθώντας τη λογική που αναπτύχθηκε για την ELHI, ο αλγόριθμος λαμβάνει υπόψη τις σύνθετες, αλλά συγκεκριμένες αλληλεπιδράσεις των αξιωμάτων της γλώσσας, ώστε να περιορίσει στο ελάχιστο την εφαρμογή των κανόνων της επίλυσης.Υλοποιήσαμε τους αλγορίθμους σε ένα πρωτότυπο σύστημα και διεξάγαμε πειραματική αξιολόγηση κάνοντας χρήση σύνθετων OWL οντολογιών μεγάλης κλίμακας. Πρόκειται για την πρώτη αξιολόγηση συστήματος επαναγραφής με οντολογίες τέτοιου μεγέθους. Στην περίπτωση των οντολογιών σε DL-Lite και ELHI τα αποτελέσματα δείχνουν ότι το σύστημά μας αποκρίνεται ταχύτερα από ότι τα διαθέσιμα εξελιγμένα συστήματα. Στις περιπτώσεις οντολογιών σε Horn-SHIQ η σύγκριση έγινε με το μοναδικό υπάρχον σύστημα που υποστηρίζει την επαναγραφή ερωτημάτων σε αυτή την εκφραστικότητα, το οποίο δεν καταφέρνει να αποκριθεί στον προκαθορισμένο χρόνο τερματισμού, όταν το σύστημά μας αποκρίνεται σε μερικά δευτερόλεπτα.