αγγλικά : Datalog
γαλλικά : Datalog
γερμανικά : Datalog
Η Datalog είναι μια γλώσσα ερωτήσεων και κανόνων για λογικές βάσεις δεδομένων (deductive databases), η οποία συντακτικά είναι υποσύνολο της Prolog. Υπάρχει από τα πρώτα χρόνια του λογικού προγραμματισμού αλλά έγινε γνωστή σαν ξεχωριστό πεδίο το 1977 όταν ο Hervé Gallaire και ο Jack Minker οργάνωσαν ένα workshop σχετικά με τη λογική και τις βάσεις δεδομένων[1]. Ο David Maier συνέλαβε την ονομασία Datalog[2].
Χαρακτηριστικά, περιορισμοί και επεκτάσεις
Η αποτίμηση των ερωτήσεων στη Datalog βασίζεται στη λογική πρώτου βαθμού και επομένως είναι συνεπής και πλήρης. Μπορεί να εκτελεστεί αποδοτικά ακόμα και για μεγάλες βάσεις δεδομένων και ακολουθεί στρατηγικές προς τα επάνω (bottom-up).
Σε αντίθεση με την Prolog:
δεν επιτρέπει πολύπλοκους όρους σαν ορίσματα σε κατηγορήματα, π.χ. το p(1, 2) επιτρέπεται αλλά όχι το p(f1(1), 2),
επιβάλλει κάποιους περιορισμούς διαστρωμάτωσης (stratification) στη χρήση της άρνησης και της αναδρομής, και
επιτρέπει μόνο μεταβλητές περιορισμένου εύρους, δηλ. κάθε μεταβλητή στο συμπέρασμα ενός κανόνα πρέπει επίσης να εμφανίζεται σε μια πρόταση χωρίς άρνηση στις προϋποθέσεις του κανόνα.
Λόγω αυτών των κανόνων το σύνολο όλων των πιθανών αποδείξεων είναι πεπερασμένο και όλα τα προγράμματα σε Datalog τερματίζουν (σε αντίθεση με τα προγράμματα σε Prolog). Αυτό έχει ως αποτέλεσμα, οι εντολές και τα κατηγορήματα ενός προγράμματος μπορούν να δοθούν με οποιαδήποτε σειρά (πάλι σε αντίθεση με την Prolog). Έχουν προταθεί διάφορες μέθοδοι για την αποδοτική εκτέλεση ερωτήσεων, π.χ. ο αλγόριθμος Magic Sets,[3] ή ο λογικός προγραμματισμός με πίνακες.[4]
Συστήματα Datalog βρίσκονται πίσω από εξειδικευμένες βάσεις δεδομένων όπως η βάση δεδομένων της Intellidimension για το σημασιολογικό ιστό. Επιπλέον, κάποια δημοφιλή συστήματα βάσεων δεδομένων περιλαμβάνουν ιδέες και αλγόριθμους που αναπτύχθηκαν για τη Datalog. Για παράδειγμα το πρότυπο SQL:1999 περιλαμβάνει αναδρομικές ερωτήσεις και ο αλγόριθμος Magic Sets (που αρχικά αναπτύχθηκε για τη γρηγορότερη αποτίμηση των ερωτήσεων της Datalog) έχει υλοποιηθεί στην DB2 της IBM.
Δύο επεκτάσεις της Datalog επιτρέπουν τη χρήση αντικειμενοστρεφούς προγραμματισμού και την πράξη Ή (σύζευξη, disjunction) σαν κεφαλή των προτάσεων. Και οι δύο επεκτάσεις αυτές έχουν σημαντικό αντίκτυπο στον ορισμό της σημασιολογίας της Datalog και στην υλοποίηση ενός διερμηνέα Datalog για αυτήν.
Παράδειγμα
Παράδειγμα προγράμματος σε Datalog:
parent(bill,mary).
parent(mary,john).
Αυτές οι δύο γραμμές ορίζουν δύο γεγονότα, δηλ. δυο πράγματα που είναι πάντα αληθή. Διαισθητικά σημαίνουν: γονιός του bill είναι η mary and γονιός της mary είναι ο john.
ancestor(X,Y) :- parent(X,Y).
ancestor(X,Y) :- parent(X,Z),ancestor(Z,Y).
Αυτές οι δύο γραμμές περιγράφουν τους κανόνες που ορίζουν τη σχέση προγόνου (ancestor). Ένας κανόνας αποτελείται από δύο κύρια μέρη που χωρίζονται από το σύμβολο :-. Το μέρος στα αριστερά του είναι η κεφαλή, το μέρος στα δεξιά του είναι το σώμα του κανόνα. Ένας κανόνας διαβάζεται (και μπορεί διαισθητικά να γίνει κατανοητός) ως εξής: <κεφαλή> αν είναι γνωστό ότι <σώμα>. Τα κεφαλαία γράμματα είναι μεταβλητές. Επομένως στο παράδειγμα ο πρώτος κανόνας μπορεί να διαβαστεί σαν ο X είναι πρόγονος του Y αν είναι γνωστό ότι ο X είναι γονιός του Y και ο δεύτερος κανόνας σαν ο X είναι πρόγονος του Y αν είναι γνωστό ότι ο X είναι γονιός κάποιου Z και ο Z είναι πρόγονος του Y. Η σειρά των προτάσεων δεν έχει σημασία στην Datalog σε αντίθεση με την Prolog, η οποία εξαρτάται από τη σειρά τους για να υπολογίσει το αποτέλεσμα της κλήσης μιας ερώτησης.
Η Datalog διακρίνει μεταξύ εκτασιακών (extensional) και νοηματικών (intensional) συμβόλων κατηγορημάτων. Σε αντίθεση με τα εκτασιακά σύμβολα κατηγορημάτων που ορίζονται μόνο από γεγονότα, τα νοηματικά σύμβολα κατηγορημάτων ορίζονται μόνο από κανόνες. Στο παραπάνω παράδειγμα το ancestor είναι νοηματικό κατηγορηματικό σύμβολο, και το parent είναι εκτασιακό. Τα κατηγορήματα μπορούν επίσης να οριστούν από γεγονότα και κανόνες και επομένως δεν είναι αμιγώς εκτασιακά ή νοηματικά, αλλά κάθε πρόγραμμα σε Datalog μπορεί να γραφτεί σαν ένα ισοδύναμο πρόγραμμα χωρίς τέτοιου είδους κατηγορήματα που να έχουν διπλούς ρόλους.
?- ancestor(bill,X).
Η παραπάνω ερώτηση ζητά όλους τους πρόγονους του bill και επιστρέφει mary και john αν εκτελεστεί σε ένα σύστημα Datalog που περιέχει τα γεγονότα και τους κανόνες που έχουν περιγραφεί παραπάνω.
Συστήματα που υλοποιούν τη Datalog
Οι περισσότερες υλοποιήσεις της Datalog προέρχονται από ακαδημαϊκά εγχειρήματα.[5] Ακολουθεί μια σύντομη λίστα από συστήματα που είτε βασίζονται στη Datalog ή παρέχουν κάποιο διερμηνέα της:
bddbddb, μια υλοποίηση της Datalog του Πανεπιστημίου Στάνφορντ. Χρησιμοποιείται κυρίως για ερωτήσεις πάνω σε κώδικα byte της Java, για παράδειγμα στην ανάλυση "δείχνει-σε" ("points-to") σε μεγάλα προγράμματα σε Java.
ConceptBase, ένα λογικό (deductive) και αντικειμενοστρεφές σύστημα βάσης δεδομένων που βασίζεται σε έναν αποτιμητή ερωτήσεων Datalog. Χρησιμοποιείται κυρίως για θεωρητική μοντελοποίηση και μετα-μοντελοποίηση.
IRIS, μια μηχανή ανοιχτού λογισμικού για Datalog που έχει υλοποιηθεί σε Java. Η IRIS επεκτείνει τη Datalog με σύμβολα συναρτήσεων, ενσωματωμένα κατηγορήματα, τοπικά διαστρωματωμένα ή μη-διαστρωματωμένα λογικά προγράμματα (με χρήση καλώς ορισμένης σημασιολογίας), μη ασφαλείς κανόνες και τύπους δεδομένων από XML σχήματα (XML schemas).
DES, μια υλοποίηση ανοιχτού κώδικα της Datalog που προορίζεται για την εκμάθηση της Datalog σε μαθήματα.
XSB, ένα σύστημα βάσης δεδομένων λογικού προγραμματισμού για Unix και Windows.
.QL, μια αντικειμενοστρεφής έκδοση της Datalog από την Semmle.
Datalog, μια ελαφρή λογική βάση δεδομένων γραμμένη σε Lua.
SecPAL, μια γλώσσα για κανόνες ασφάλειας που αναπτύχθηκε από τη Microsoft Research.[6]
DLV, μια επέκταση της Datalog που επιτρέπει προτάσεις κεφαλής που περιλαμβάνουν σύζευξη.
Datalog for Racket, μια υλοποίηση της Datalog για τη γλώσσα προγραμματισμού Racket.
Clojure Datalog, μια προσφερόμενη (contributed) βιβλιοθήκη της Clojure που υλοποιεί κάποια χαρακτηριστικά της Datalog.
Cascalog, μια βιβλιοθήκη της Clojure για την ερώτηση σε δεδομένα που είναι αποθηκευμένα σε συστοιχίες Hadoop.
OverLog, μια υλοποίηση της Datalog για δίκτυα ενσωματωμένα σε άλλα δίκτυα (overlay networks).
LogicBlox, μια εμπορική υλοποίηση της Datalog που χρησιμοποιείται για το σχεδιασμό πωλήσεων μέσω Web και για εφαρμογές ασφάλισης.
Το πλαίσιο σημασιολογικού ιστού Jena περιλαμβάνει μια υλοποίηση της Datalog σαν μέρος της μηχανής γενικών κανόνων του, η οποία επίσης αποτελεί την υλοποίηση της υποστήριξης για OWL και RDFS.[7]
Meld, μια επέκταση της Datalog για τον προγραμματισμό κατανεμημένων συστημάτων.
Η Intellidimension, παρέχει αρκετές εμπορικές υλοποιήσεις της μηχανής της Datalog βασισμένης σε πρότυπα του Σημασιολογικού Ιστού.
Δείτε επίσης
IBM DB2
Υποσημειώσεις
Hervé Gallaire, Jack Minker (Εκδότες): Logic and Data Bases, Symposium on Logic and Data Bases, Centre d'études et de recherches de Toulouse, 1977. Advances in Data Base Theory, Plenum Press, New York, 1978, ISBN 0-306-40060-X.
Serge Abiteboul, Richard Hull, Victor Vianu: Foundations of databases. σελ.305 [1].
Banilhon, "Magic sets and other strange ways to implement logic programs Αρχειοθετήθηκε 2012-03-08 στο Wayback Machine."
Frank Pfenning and Carsten Schuermann Twelf User's Guide
«ACM SIGMOD Database Software». Αρχειοθετήθηκε από το πρωτότυπο στις 15 Μαρτίου 2010. Ανακτήθηκε στις 4 Ιουλίου 2010.
«SecPAL». Microsoft Research. Αρχειοθετήθηκε από το πρωτότυπο στις 23 Φεβρουαρίου 2007. Ανακτήθηκε στις 4 Ιουλίου 2010.
«Jena».
S Ceri, G Gottlob, L Tanca, "What you always wanted to know about Datalog (and never dared to ask)". IEEE Transactions on Knowledge and Data Engineering 1(1), 1989, pp. 146–66.
Hellenica World - Scientific Library
Από τη ελληνική Βικιπαίδεια http://el.wikipedia.org . Όλα τα κείμενα είναι διαθέσιμα υπό την GNU Free Documentation License
