Boolean conjunctive query: Difference between revisions

Revision as of 02:46, 21 July 2007

Latest revision as of 05:13, 14 January 2025

(18 intermediate revisions by 16 users not shown)

Line 1:

In the theory of [[relational databases]], a '''Boolean conjunctive query''' is a [[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]] of variables and constants; the number of elements in <math>t_i</math> is equal to the [[arity]] of <math>R_i</math>. Such a query evaluates to either true or false depending on whether the relations in the database containscontain the appropriate tuples of values, i.e. the conjunction is [[Validity (logic)|valid]] according to the facts in the database.

As an example, if a [[database schema]] contains the relation symbols <math>{{mvar|Father</math>}} (binary, who's the father of whowhom) and <math>Employeed</math>{{mvar|Employed}} (unary, who is employeedemployed), a conjunctive query could be <math>Father(\text{Mark}, x) \wedge EmployeedEmployed(x)</math>. This query evaluates to true if there exists an individual <math>{{mvar|x</math>}} who is a child of Mark and employed. In other worldswords, this query expresses the question: "dodoes Mark have an employed childrenchild?"

== Complexity ==

{{Main|Conjunctive query#Complexity}}

==See also==

*[[Logical conjunction]]

*[[Conjunctive query]]

==References==

* {{cite journal|

| author author1= G. Gottlob, |author2=N. Leone, |author3=F. Scarcello | title = The complexity of acyclic conjunctive queries

| journal = Journal of the ACM (JACM)

| title = The complexity of acyclic conjunctive queries

| journal = Journal of the ACM (JACM)

| volume = 48

| issue = 3

| pages = 431-498431–498

| year = 2001

| doi = 10.1145/382780.382783

}}

{{Uncategorized|date=July 2007}}

[[Category:Boolean algebra]]