In the theory of

relational databases A relational database is a (most commonly digital) database based on the relational model of data, as proposed by E. F. Codd in 1970. A system used to maintain relational databases is a relational database management system (RDBMS). Many relatio ...

, a Boolean conjunctive query is a

conjunctive query In database theory, a conjunctive query is a restricted form of first-order queries using the logical conjunction operator. Many first-order queries can be written as conjunctive queries. In particular, a large part of queries issued on relational ...

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 In mathematics, a tuple is a finite ordered list (sequence) of elements. An -tuple is a sequence (or ordered list) of elements, where is a non-negative integer. There is only one 0-tuple, referred to as ''the empty tuple''. An -tuple is defi ...

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 contain the appropriate tuples of values, i.e. the conjunction is valid according to the facts in the database. As an example, if a database schema contains the relation symbols (binary, who's the father of whom) and (unary, who is employed), a conjunctive query could be

Father(\text, x) \wedge Employed(x)

. This query evaluates to true if there exists an individual who is a child of Mark and employed. In other words, this query expresses the question: "does Mark have an employed child?"

References

* {{cite journal , author1=G. Gottlob , author2=N. Leone , author3=F. Scarcello , title = The complexity of acyclic conjunctive queries , journal = Journal of the ACM , volume = 48 , issue = 3 , pages = 431–498 , year = 2001 , doi = 10.1145/382780.382783 Boolean algebra

See also

References