HOME

TheInfoList



Click Here for Items Related To - Boolean conjunctive query
OR:
Boolean conjunctive query on:   [Wikipedia]   [Google]   [Amazon]

In the theory of relational databases, 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 sequence or ''ordered list'' of numbers or, more generally, mathematical objects, which are called the ''elements'' of the tuple. An -tuple is a tuple of elements, where is a non-negative integer. There is o ...
of variables and constants; the number of elements in t_i is equal to the
arity In logic, mathematics, and computer science, arity () is the number of arguments or operands taken by a function, operation or relation. In mathematics, arity may also be called rank, but this word can have many other meanings. In logic and ...
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 The database schema is the structure of a database described in a formal language supported typically by a relational database management system (RDBMS). The term "wikt:schema, schema" refers to the organization of data as a blueprint of how the ...
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?"


Complexity


See also

*
Logical conjunction In logic, mathematics and linguistics, ''and'' (\wedge) is the Truth function, truth-functional operator of conjunction or logical conjunction. The logical connective of this operator is typically represented as \wedge or \& or K (prefix) or ...
*
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 ...


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