Μετασχηματισμοί Προγραμμάτων Στις Επαγωγικές Βάσεις Δεδομένων Με Χρήση Του Νοηματικού Λογικού Προγραμματισμού.

Abstract

Η εργασία αυτή μελετάει τη σχέση ανάμεσα σε προγράμματα Datalog και προγράμματα του νοηματικού λογικούπρογραμματισμού (intensional logic programming). Πιο συγκεκριμένα, παρουσιάζονται μετασχηματισμοί κλάσεων προγραμμάτων Datalog σε προγράμματα Datalog_{nS} και Choice Datalog_{nS}, που είναι γλώσσες χρονικού λογικού προγραμματισμού. Οι νέοι μετασχηματισμοί ανήκουν στηνκατηγορία βελτιστοποίησης προγραμμάτων σε επαγωγικές βάσειςδεδομένων μέσω της διάδοσης των τιμών, στην οποία οι τιμέςεισόδου του στόχου του αρχικού προγράμματος διαδίδονται έτσι ώστε να περιορίζονται τα παραγόμενα άτομα κατά την από-κάτω-προς-τα-πάνω (bottom-up) εκτέλεση του νέου προγράμματος. Η από-κάτω-προς-τα-πάνω (bottom-up) αποτίμηση του τελικού προγράμματος μιμείται την από-πάνω-προς-τα-κάτω (top-down) αποτίμηση του αρχικού προγράμματος, συνδυάζοντας τα πλεονεκτήματα των δύο αυτών τρόπων αποτίμησης. Παράλληλα, το αρχικό και το τελικό πρόγραμμα είναι σημασιολογικά ισοδύναμα.Η αφετηρία των μετασχηματισμών που παρουσιάζονται είναι ομετασχηματισμός διακλαδιζόμενου χρόνου (branching-timetransformation) \cite{RG01-71,RG98-55}. Η κλάση των Datalogπρογραμμάτων στην οποία μπορεί να εφαρμοστεί ο μετασχηματισμός διακλαδιζόμενου χρόνου, είναι τα Chain Datalog προγράμματα, μια κλάση που έχει ιδιαίτερο ενδιαφέρον \cite{Yan90-230,GSZ99-349} και αντιστοιχεί στις γραμματικές χωρίς συμφραζόμενα (context free grammars). Ο μετασχηματισμός επεκτείνεται ώστε να εφαρμόζεται σεμια ευρύτερη κλάση προγραμμάτων Datalog. Αυτή η κλάσηπρογραμμάτων, που αποτελεί ένα γνήσιο υπερσύνολο των ChainDatalog προγραμμάτων, είναι αυτή στην οποία επιτρέπονται πολλαπλές καταναλώσεις μεταβλητών. Για το χειρισμό αυτών τωνπρογραμμάτων \cite{PRG02-25,PGR04,PRG06}, χρειάζεται να χρησιμοποιηθούν γλώσσες που υποστηρίζουν μη-ντετερμινιστικές κατασκευές, ειδικότερα τα κατηγορήματα επιλογής (choicepredicates) \cite{OW94-877}. Κύριο χαρακτηριστικό τους είναι ότι σε ένα συγκεκριμένο περιβάλλον (context), παίρνουν μοναδική τιμή. Καταρχήν, ορίζονται οι αρχικές και οι τελικές γλώσσες των μετασχηματισμών καθώς και η σημασιολογία τους. Κατόπιν παρουσιάζονται οι αλγόριθμοι των νέων μετασχηματισμών και αποδεικνύεται η ορθότητά τους. Στη συνέχεια προτείνονται εκλεπτύνσεις των αλγορίθμων που αυξάνουν την απόδοση της \tl{bottom-up} εκτέλεσης των τελικών προγραμμάτων. Επιπλέον, παρουσιάζεται μια βελτιστοποιημένη αποδεικτική διαδικασία που εφαρμόζεται στα τελικά προγράμματα, η οποία πάντοτε τερματίζει. Τέλος, συγκρίνονται οι νέοι μετασχηματισμοί με τους ήδη υπάρχοντες και τα αποτελέσματα αυτής της σύγκρισης δείχνουν πως αυτοί έχουν πρακτική σπουδαιότητα, εκτός από την θεωρητική τους σημασία.Κλείνοντας, παραθέτονται τα αποτελέσματα της διδακτορικής διατριβής και προτείνονται μελλοντικές ερευνητικές κατευθύνσεις. Ενδιαφέρον θα είχε να μελετηθούν προγράμματα στα οποία έχουμε διαφορετικούς τρόπους καταναλώσεων μεταβλητών (π.χ. περισσότερα ορίσματα εξόδου) ώστε να εφαρμόζονται σε όλη τη Datalog και προγράμματα με συναρτησιακά σύμβολα (γενικά λογικά προγράμματα). Ακόμα, η υλοποίηση του bottom-up υπολογισμού των τελικών προγραμμάτων θα μας επέτρεπε να πειραματιστούμε με ένα μεγάλο αριθμό προγραμμάτων και βάσεων δεδομένων και να συγκρίνουμε τους προτεινόμενους μετασχηματισμούς με άλλες γνωστές τεχνικές της περιοχής, αναδεικνύοντας τα πλεονεκτήματα και τα μειονεκτήματα της κάθε προσέγγισης. Τέλος, θα πρέπει να εξεταστεί η δυνατότητα εφαρμογής αυτών των μετασχηματισμών σε νέες περιοχές που σχετίζονται με την εξαγωγή γνώσης με χρήση της μαθηματικής λογικής, όπως είναι ο Σημασιολογικός Ιστός (Semantic Web).