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

Abstract

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