Boolean conjunctive query

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 Ri is a relation symbol and each ti is a tuple of variables and constants; the number of elements in ti is equal to the arity of Ri. 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?"

See also

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. 

Wikimedia Foundation. 2010.

Игры ⚽ Поможем решить контрольную работу

Look at other dictionaries:

  • Conjunctive query — In database theory, a conjunctive query is a restricted form of first order queries. A large part of queries issued on relational databases can be written as conjunctive queries, and large parts of other first order queries can be written as… …   Wikipedia

  • List of Boolean algebra topics — This is a list of topics around Boolean algebra and propositional logic. Contents 1 Articles with a wide scope and introductions 2 Boolean functions and connectives 3 Examples of Boolean algebras …   Wikipedia

  • Boolean algebra (introduction) — Boolean algebra, developed in 1854 by George Boole in his book An Investigation of the Laws of Thought , is a variant of ordinary algebra as taught in high school. Boolean algebra differs from ordinary algebra in three ways: in the values that… …   Wikipedia

  • Boolean algebra — This article discusses the subject referred to as Boolean algebra. For the mathematical objects, see Boolean algebra (structure). Boolean algebra, as developed in 1854 by George Boole in his book An Investigation of the Laws of Thought,[1] is a… …   Wikipedia

  • Outline of logic — The following outline is provided as an overview of and topical guide to logic: Logic – formal science of using reason, considered a branch of both philosophy and mathematics. Logic investigates and classifies the structure of statements and… …   Wikipedia

  • List of mathematics articles (B) — NOTOC B B spline B* algebra B* search algorithm B,C,K,W system BA model Ba space Babuška Lax Milgram theorem Baby Monster group Baby step giant step Babylonian mathematics Babylonian numerals Bach tensor Bach s algorithm Bachmann–Howard ordinal… …   Wikipedia

  • List of NP-complete problems — Here are some of the more commonly known problems that are NP complete when expressed as decision problems. This list is in no way comprehensive (there are more than 3000 known NP complete problems). Most of the problems in this list are taken… …   Wikipedia

  • Logical conjunction — ∧ redirects here. For exterior product, see exterior algebra. Venn diagram of …   Wikipedia

  • RDFLib — Infobox Software name = RDFLib developer = Daniel Krech latest release version = 2.4.0 latest release date = April 4, 2007 operating system = Cross platform genre = Library license = BSD website = [http://rdflib.net/ http://rdflib.net/] RDFLib is …   Wikipedia

  • Complexity of constraint satisfaction — The complexity of constraint satisfaction is the application of computational complexity theory on constraint satisfaction. It has mainly been studied for discriminating between tractable and intractable classes of constraint satisfaction… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”