Editing Logic programming (section)

=== Datalog ===
{{Main|Datalog}}
Datalog is a database definition language, which combines a relational view of data, as in [[relational database]]s, with a logical view, as in logic programming.

Relational databases use a relational calculus or relational algebra, with [[Relational database#Relational operations|relational operations]], such as ''union'', ''intersection'', ''set difference'' and ''cartesian product'' to specify queries, which access  a database. Datalog uses logical connectives, such as ''or'', ''and'' and ''not'' in the bodies of rules to define relations as part of the database itself.

It was recognized early in the development of relational databases that recursive queries cannot be expressed in either relational algebra or relational calculus, and that this defficiency can be remedied by introducing a least-fixed-point operator.<ref>Aho, A.V. and Ullman, J.D., 1979, January. Universality of data retrieval languages. In Proceedings of the 6th ACM SIGACT-SIGPLAN symposium on Principles of programming languages (pp. 110-119).</ref><ref>Maier, D., Tekle, K.T., Kifer, M. and Warren, D.S., 2018. Datalog: concepts, history, and outlook. In Declarative Logic Programming: Theory, Systems, and Applications (pp. 3-100).</ref> In contrast, recursive relations can be defined naturally by rules in logic programs, without the need for any new logical connectives or operators.

Datalog differs from more general logic programming by having only constants and variables as terms. Moreover, all facts are variable-free, and rules are restricted, so that if they are executed bottom-up, then the derived facts are also variable-free.

For example, consider the family database:

<syntaxhighlight lang="prolog">
mother_child(elizabeth, charles).
father_child(charles, william).
father_child(charles, harry).
parent_child(X, Y) :- 
     mother_child(X, Y).
parent_child(X, Y) :- 
     father_child(X, Y).
ancestor_descendant(X, Y) :- 
     parent_child(X, X).
ancestor_descendant(X, Y) :- 
     ancestor_descendant(X, Z), 
     ancestor_descendant(Z, Y).
</syntaxhighlight>

Bottom-up execution derives the following set of additional facts and terminates:

<syntaxhighlight lang="prolog">
parent_child(elizabeth, charles).
parent_child(charles, william).
parent_child(charles, harry).

ancestor_descendant(elizabeth, charles).
ancestor_descendant(charles, william).
ancestor_descendant(charles, harry).

ancestor_descendant(elizabeth, william).
ancestor_descendant(elizabeth, harry).
</syntaxhighlight>

Top-down execution derives the same answers to the query:
<syntaxhighlight lang="prolog">
?- ancestor_descendant(X, Y).
</syntaxhighlight>

But then it goes into an infinite loop. However, top-down execution with [[Tabled logic programming|tabling]] gives the same answers and terminates without looping.