Boolean conjunctive query: Difference between revisions
imported>QCDvac correction |
url |
||
| Line 1: | Line 1: | ||
{{Short description|Query returning true/false based on whether a conjunction of conditions holds}} | |||
In the theory of relational databases, a '''Boolean conjunctive query''' is a [[Conjunctive query|conjunctive query]] without distinguished predicates, i.e., a query in the form <math>R_1(t_1) \wedge \cdots \wedge R_n(t_n)</math>, where each <math>R_i</math> is a relation symbol and each <math>t_i</math> is a [[Tuple|tuple]] of variables and constants; the number of elements in <math>t_i</math> is equal to the [[Arity|arity]] of <math>R_i</math>. 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 [[Philosophy:Validity (logic)|valid]] according to the facts in the database. | In the theory of relational databases, a '''Boolean conjunctive query''' is a [[Conjunctive query|conjunctive query]] without distinguished predicates, i.e., a query in the form <math>R_1(t_1) \wedge \cdots \wedge R_n(t_n)</math>, where each <math>R_i</math> is a relation symbol and each <math>t_i</math> is a [[Tuple|tuple]] of variables and constants; the number of elements in <math>t_i</math> is equal to the [[Arity|arity]] of <math>R_i</math>. 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 [[Philosophy:Validity (logic)|valid]] according to the facts in the database. | ||
As an example, if a [[Database schema|database schema]] contains the relation symbols {{mvar|Father}} (binary, who's the father of whom) and {{mvar|Employed}} (unary, who is employed), a conjunctive query could be <math>Father(\text{Mark}, x) \wedge Employed(x)</math>. This query evaluates to true if there exists an individual {{mvar|x}} who is a child of Mark and employed. In other words, this query expresses the question: "does Mark have an employed child?" | As an example, if a [[Database schema|database schema]] contains the relation symbols {{mvar|Father}} (binary, who's the father of whom) and {{mvar|Employed}} (unary, who is employed), a conjunctive query could be <math>Father(\text{Mark}, x) \wedge Employed(x)</math>. This query evaluates to true if there exists an individual {{mvar|x}} who is a child of Mark and employed. In other words, this query expresses the question: "does Mark have an employed child?" | ||
Latest revision as of 23:27, 14 April 2026
In the theory of relational databases, a Boolean conjunctive query is a conjunctive query without distinguished predicates, i.e., a query in the form , where each is a relation symbol and each is a tuple of variables and constants; the number of elements in is equal to the arity of . 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 Father (binary, who's the father of whom) and Employed (unary, who is employed), a conjunctive query could be . 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 an employed child?"
Complexity
See also
References
- G. Gottlob; N. Leone; F. Scarcello (2001). "The complexity of acyclic conjunctive queries". Journal of the ACM 48 (3): 431–498. doi:10.1145/382780.382783.
 |  |
