ΗDatalog είναι μια γλώσσα ερωτήσεων και κανόνων για λογικές βάσεις δεδομένων (deductive databases), η οποία συντακτικά είναι υποσύνολο τηςProlog. Υπάρχει από τα πρώτα χρόνια τουλογικού προγραμματισμού αλλά έγινε γνωστή σαν ξεχωριστό πεδίο το 1977 όταν οHervé Gallaire και οJack Minker οργάνωσαν ένα workshop σχετικά με τηλογική και τιςβάσεις δεδομένων[1]. Ο David Maier συνέλαβε την ονομασία Datalog[2].
Η αποτίμηση των ερωτήσεων στη Datalog βασίζεται στηλογική πρώτου βαθμού και επομένως είναι συνεπής και πλήρης. Μπορεί να εκτελεστεί αποδοτικά ακόμα και για μεγάλες βάσεις δεδομένων και ακολουθεί στρατηγικές προς τα επάνω (bottom-up).
Σε αντίθεση με την Prolog:
Λόγω αυτών των κανόνων το σύνολο όλων των πιθανών αποδείξεων είναι πεπερασμένο και όλα τα προγράμματα σε 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 προέρχονται από ακαδημαϊκά εγχειρήματα.[5] Ακολουθεί μια σύντομη λίστα από συστήματα που είτε βασίζονται στη Datalog ή παρέχουν κάποιο διερμηνέα της: