Boolean conjunctive query

In the theory of relational databases, a Boolean conjunctive query is a query in the form $R_{1}(t_{1})\wedge \cdots \wedge R_{n}(t_{n})$, where each $R_{i}$ is a relation symbol and each $t_{i}$ is a tuple of variables and constants; the number of elements in $t_{i}$ is equal to the arity of $R_{i}$. Such a query evaluates to either true or false depending on whether the relations in the database contains the appropriate tuples of values.

As an example, if a database schema contains the relation symbols $Father$ (binary, who's the father of who) and $Employeed$ (unary, who is employeed), a conjunctive query could be $Father(Mark,x)\wedge Employeed(x)$. This query evaluates to true if there exists an individual $x$ who is a child of Mark and employed. In other worlds, this query expresses the question: "do Mark have employed children?"

See also

• Logical conjunction

References

• G. Gottlob, N. Leone, F. Scarcello (2001). "The complexity of acyclic conjunctive queries". Journal of the ACM (JACM). 48 (3): 431–498. doi:10.1145/382780.382783. {{cite journal}}: Cite has empty unknown parameter: |1= (help)CS1 maint: multiple names: authors list (link)