Αλγόριθμοι επανεγγραφής τροποποιημένων ερωτημάτων για βατές περιγραφικές λογικές
Authors: Βενέτης Αναστάσιος 
Published: September 2021

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