Boolean conjunctive query

In the theory of relational databases, a Boolean conjunctive query is a conjunctive query without distinguished predicates, i.e., 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 whom) and $Employed$ (unary, who is employed), a conjunctive query could be $Father(Mark, x) \wedge Employed(x)$ . This query evaluates to true if there exists an individual $x$ who is a child of Mark and employed. In other words, this query expresses the question: "does Mark have employed children?"

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.

Boolean conjunctive query

See also

References