Conjunctive Queries and Datalog
Besides their logical notation, conjunctive queries can also be written as datalog rules. Many authors in fact prefer the following datalog notation for the query above:
result(student, address) :- attends(student, course), gender(student, male), attends(student2, course), gender(student2, female), lives(student, address).
Although there are no quantifiers in this notation, variables appearing in the head of the rule are still implicitly universally quantified, while variables only appearing in the body of the rule are still implicitly existentially quantified.
While any conjunctive query can be written as a datalog rule, not every datalog program can be written as a conjunctive query. In fact, only single rules over extensional predicate symbols can be easily rewritten as an equivalent conjunctive query. The problem of deciding whether for a given datalog program there is an equivalent nonrecursive program (corresponding to a positive relational algebra query, or, equivalently, a formula of positive existential first-order logic, or, as a special case, a conjunctive query) is known as the datalog boundedness problem and is undecidable.
Read more about this topic: Conjunctive Query
Famous quotes containing the word queries:
“All I can say, in answer to this kind queries [of friends] is that I have not the distemper called the Plague; but that I have all the plagues of old age, and of a shattered carcase.”
—Philip Dormer Stanhope, 4th Earl Chesterfield (1694–1773)