Please use this identifier to cite or link to this item: http://artemis.cslab.ece.ntua.gr:8080/jspui/handle/123456789/8937
Title: Αλγόριθμοι Επανεγγραφής Τροποποιημένων Ερωτημάτων Για Βατές Περιγραφικές Λογικές
Authors: Αναστάσιος Βενέτης
Στάμου Γιώργος
Keywords: semantic web
dl-lite
datalog
query rewriting
query refinement
ontology based data access
query answering
Issue Date: 24-Jan-2014
Abstract: Το πρόβλημα συλλογιστικής της απάντησης συζευκτικών ερωτημάτων πάνω απόβάσεις γνώσης Περιγραφικών Λογικών, μέσω της επανεγγραφής ερωτημάτων, έχειπαρουσιάσει ιδιαίτερη άνθιση τα τελευταία χρόνια. Δεδομένου ενός συζευκτικούερωτήματος και μιας βάσης γνώσης (TBox και ABox) μια διαδικασία επανεγγραφήςερωτημάτων παράγει ένα νέο ερώτημα που ενσωματώνει τους περιορισμούς της βάσηςγνώσης που περιέχονται στο TBox, έτσι ώστε για οποιοδήποτε ABox (σύνολοδεδομένων) η αποτίμηση του αρχικού ερωτήματος πάνω στο TBox και το ABox ναμπορεί να υπολογιστεί με την αποτίμηση μόνο του νέου ερωτήματος πάνω στο ABox.Επειδή η πολυπλοκότητα απάντησης ερωτημάτων σε εκφραστικές ΠεριγραφικέςΛογικές είναι απαγορευτική έχουν αναπτυχθεί γλώσσες Περιγραφικών Λογικών πουείναι βατές, όπως η οικογένεια γλωσσών DL-Lite, η EL και η οικογένεια τηςDatalog+- για τις οποίες έχει παρουσιαστεί πληθώρα αλγορίθμων/συστημάτωνεπανεγγραφής ερωτημάτων. Όμως, όλοι οι αλγόριθμοι που γνωρίζουμε εκτελούνταικάθε φορά από την αρχή χωρίς να λαμβάνουν υπ' όψιν και να εκμεταλλεύονταιπροηγούμενες εκτελέσεις, ακόμα και εάν διαδοχικά ερωτήματα έχουν πολύ μικρέςδιαφορές, κάτι το οποίο είναι ιδιαίτερα συχνό στο διαδίκτυο.Στην παρούσα διατριβή μελετάμε το πρόβλημα της επανεγγραφής ερωτημάτων τα οποίαέχουν τροποποιηθεί με διάφορους τρόπους. Οι τρόποι αυτοί αφορούν στην προσθήκηή αφαίρεση διακεκριμένων μεταβλητών ή ατόμων. Πιο συγκεκριμένα, μελετάμε τοπρόβλημα υπολογισμού της επανεγγραφής ενός τροποποιημένου ερωτήματοςεκμεταλλευόμενοι την επανεγγραφή που έχει υπολογιστεί για το αρχικό ερώτημα,αποφεύγοντας έτσι να την υπολογίσουμε εξαρχής. Στη συνέχεια παρουσιάζουμεβελτιστοποιήσεις οι οποίες αυξάνουν σημαντικά την απόδοση των αλγορίθμων μας.Ακολούθως, μειώνουμε την εκφραστικότητα των οντολογιών που μελετάμε στη γλώσσαDL-LiteR έτσι ώστε να βελτιστοποιήσουμε περαιτέρω το πρόβλημα του υπολογισμούτης επανεγγραφής ενός ερωτήματος στο οποίο έχει προστεθεί ένα άτομο. Αυτό πουπαρουσιάζει ιδιαίτερο ενδιαφέρον είναι πως οι τεχνικές μας θέτουν τις βάσειςγια έναν πρωτότυπο επαυξητικό αλγόριθμο επανεγγραφής σταθερών ερωτημάτων γιαοντολογίες DL-LiteR. Πιο συγκεκριμένα, το ερώτημα μπορεί να «αναλυθεί» σταάτομα του και στη συνέχεια να επεξεργαστούμε κάθε άτομο επαυξητικά.Παρουσιάζουμε αναλυτικούς αλγόριθμους καθώς και ένα σύνολο από βελτιστοποιήσειςοι οποίες όπως φαίνεται και από την πειραματική μας αξιολόγηση βελτιώνουν τηναπόδοση του συστήματος μας και το καθιστούν ταχύτερο από όλα τα γνωστάσυστήματα.Τέλος, στη διατριβή αυτή μελετάμε το πρόβλημα απάντησης ερωτημάτων πάνω από έναδίκτυο οντολογιών. Ειδικότερα, μελετάμε πως η Ασαφής Συνολοθεωρία και η ΑσαφήςΛογική μπορούν να χρησιμοποιηθούν για την απόδοση σημασιολογίας και τηνεπικύρωση των αντιστοιχίσεων ανάμεσα σε δύο οντολογίες ώστε να μπορέσουμε ναεπιλύσουμε ασυνέπειες που μπορεί να προκύψουν από την αντιστοίχιση τους. Αφούλοιπόν επιλύσουμε τις ασυνέπειες αυτές χρησιμοποιούμε τις δύο αυτές οντολογίεςγια να κατασκευάσουμε μια νέα (ασαφή) οντολογία η οποία είναι συνεπής και τοABox της οποίας περιέχει αναθέσεις που έχουν προκύψει από την ερμηνεία τωνασαφών αντιστοιχίσεων και από τις δύο αρχικές οντολογιές κάνοντας έτσι εφικτήτην απάντηση ερωτημάτων.
URI: http://artemis-new.cslab.ece.ntua.gr:8080/jspui/handle/123456789/8937
Appears in Collections:Διδακτορικές Διατριβές - Ph.D. Theses

Files in This Item:
File SizeFormat 
PD2014-0007.pdf1.21 MBAdobe PDFView/Open


Items in Artemis are protected by copyright, with all rights reserved, unless otherwise indicated.