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

Abstract

Το πρόβλημα συλλογιστικής της απάντησης συζευκτικών ερωτημάτων πάνω απόβάσεις γνώσης Περιγραφικών Λογικών, μέσω της επανεγγραφής ερωτημάτων, έχειπαρουσιάσει ιδιαίτερη άνθιση τα τελευταία χρόνια. Δεδομένου ενός συζευκτικούερωτήματος και μιας βάσης γνώσης (TBox και ABox) μια διαδικασία επανεγγραφήςερωτημάτων παράγει ένα νέο ερώτημα που ενσωματώνει τους περιορισμούς της βάσηςγνώσης που περιέχονται στο TBox, έτσι ώστε για οποιοδήποτε ABox (σύνολοδεδομένων) η αποτίμηση του αρχικού ερωτήματος πάνω στο TBox και το ABox ναμπορεί να υπολογιστεί με την αποτίμηση μόνο του νέου ερωτήματος πάνω στο ABox.Επειδή η πολυπλοκότητα απάντησης ερωτημάτων σε εκφραστικές ΠεριγραφικέςΛογικές είναι απαγορευτική έχουν αναπτυχθεί γλώσσες Περιγραφικών Λογικών πουείναι βατές, όπως η οικογένεια γλωσσών DL-Lite, η EL και η οικογένεια τηςDatalog+- για τις οποίες έχει παρουσιαστεί πληθώρα αλγορίθμων/συστημάτωνεπανεγγραφής ερωτημάτων. Όμως, όλοι οι αλγόριθμοι που γνωρίζουμε εκτελούνταικάθε φορά από την αρχή χωρίς να λαμβάνουν υπ' όψιν και να εκμεταλλεύονταιπροηγούμενες εκτελέσεις, ακόμα και εάν διαδοχικά ερωτήματα έχουν πολύ μικρέςδιαφορές, κάτι το οποίο είναι ιδιαίτερα συχνό στο διαδίκτυο.Στην παρούσα διατριβή μελετάμε το πρόβλημα της επανεγγραφής ερωτημάτων τα οποίαέχουν τροποποιηθεί με διάφορους τρόπους. Οι τρόποι αυτοί αφορούν στην προσθήκηή αφαίρεση διακεκριμένων μεταβλητών ή ατόμων. Πιο συγκεκριμένα, μελετάμε τοπρόβλημα υπολογισμού της επανεγγραφής ενός τροποποιημένου ερωτήματοςεκμεταλλευόμενοι την επανεγγραφή που έχει υπολογιστεί για το αρχικό ερώτημα,αποφεύγοντας έτσι να την υπολογίσουμε εξαρχής. Στη συνέχεια παρουσιάζουμεβελτιστοποιήσεις οι οποίες αυξάνουν σημαντικά την απόδοση των αλγορίθμων μας.Ακολούθως, μειώνουμε την εκφραστικότητα των οντολογιών που μελετάμε στη γλώσσαDL-LiteR έτσι ώστε να βελτιστοποιήσουμε περαιτέρω το πρόβλημα του υπολογισμούτης επανεγγραφής ενός ερωτήματος στο οποίο έχει προστεθεί ένα άτομο. Αυτό πουπαρουσιάζει ιδιαίτερο ενδιαφέρον είναι πως οι τεχνικές μας θέτουν τις βάσειςγια έναν πρωτότυπο επαυξητικό αλγόριθμο επανεγγραφής σταθερών ερωτημάτων γιαοντολογίες DL-LiteR. Πιο συγκεκριμένα, το ερώτημα μπορεί να «αναλυθεί» σταάτομα του και στη συνέχεια να επεξεργαστούμε κάθε άτομο επαυξητικά.Παρουσιάζουμε αναλυτικούς αλγόριθμους καθώς και ένα σύνολο από βελτιστοποιήσειςοι οποίες όπως φαίνεται και από την πειραματική μας αξιολόγηση βελτιώνουν τηναπόδοση του συστήματος μας και το καθιστούν ταχύτερο από όλα τα γνωστάσυστήματα.Τέλος, στη διατριβή αυτή μελετάμε το πρόβλημα απάντησης ερωτημάτων πάνω από έναδίκτυο οντολογιών. Ειδικότερα, μελετάμε πως η Ασαφής Συνολοθεωρία και η ΑσαφήςΛογική μπορούν να χρησιμοποιηθούν για την απόδοση σημασιολογίας και τηνεπικύρωση των αντιστοιχίσεων ανάμεσα σε δύο οντολογίες ώστε να μπορέσουμε ναεπιλύσουμε ασυνέπειες που μπορεί να προκύψουν από την αντιστοίχιση τους. Αφούλοιπόν επιλύσουμε τις ασυνέπειες αυτές χρησιμοποιούμε τις δύο αυτές οντολογίεςγια να κατασκευάσουμε μια νέα (ασαφή) οντολογία η οποία είναι συνεπής και τοABox της οποίας περιέχει αναθέσεις που έχουν προκύψει από την ερμηνεία τωνασαφών αντιστοιχίσεων και από τις δύο αρχικές οντολογιές κάνοντας έτσι εφικτήτην απάντηση ερωτημάτων.