Boolean Conjunctive Query¶

A closed positive existential formula made from a finite conjunction of relational atoms, returning true exactly when one assignment satisfies every atom in a database instance.

Version: v1 · 2026-09-28 · History
Domain-specific #: 8245
Domain group: Applied Sciences & Engineering
Origin domain: Computer Science & Software Engineering
Subdomain: Database Theory → Computer Science & Software Engineering
Aliases: BCQ, Boolean CQ, Existential Conjunctive Query

Core Idea¶

A Boolean conjunctive query (BCQ) is a closed positive existential formula over a relational database. Its body is a finite conjunction of well-typed relational atoms, and every variable is existentially bound. It asks whether at least one assignment of database values makes all atoms true together. Because it exposes no distinguished output variables, its result is simply true or false.

For a schema with Father(parent, child) and Employed(person),

∃x (Father(Mark, x) ∧ Employed(x))

is true exactly when one person can fill x in both atoms. Finding some child of Mark and, separately, some employed person is insufficient: variable sharing requires a single consistent witness.

The same recognition test can be expressed structurally. Treat the query atoms as a small canonical database. The BCQ holds on an instance exactly when there is a homomorphism from that canonical database to the instance, preserving relation labels, constants, and repeated-variable equalities. This equivalence makes BCQs central to query evaluation, containment, finite-model reasoning, and constraint checking.

“Boolean” describes the output arity, not an unrestricted connective vocabulary. Ordinary BCQs use conjunction and existential quantification; adding negation, disjunction, aggregation, recursion, or free output variables changes the query class.

How would you explain it like I'm…

Same-Kid Yes-No Question

A Boolean conjunctive query is a yes-or-no question like: 'Is there one kid in the class who is wearing red AND has a pet dog?' It only answers yes or no. And the same kid has to do both — one kid in red and a different kid with a dog does not count.

All-At-Once Yes/No Question

A Boolean conjunctive query is a yes-or-no question you ask a database. It is built by joining simple facts with AND and asking whether some things exist that make all of them true at once. For example: does some person exist who is a child of Mark and is employed? Finding one child of Mark and a different employed person does not count; one person has to fill both spots. The query never lists names back to you, it just says yes or no.

Existential And-Only Query

A Boolean conjunctive query is a database query made only of relational facts joined with AND, where every variable is bound by 'there exists.' Because no variable is left free for output, the query returns only true or false: is there at least one way to assign database values to the variables that makes every atom true together? For ∃x (Father(Mark, x) ∧ Employed(x)), the shared x forces one person to satisfy both conditions. 'Boolean' refers to the yes/no output, not to allowing any logical connective — adding OR, NOT, counting, recursion or output variables gives a different kind of query.

A Boolean conjunctive query (BCQ) is a closed positive existential formula over a relational schema: a finite conjunction of well-typed relational atoms in which every variable is existentially quantified. With no free (distinguished) variables, its answer on a database is simply true or false — true when some assignment of domain values satisfies all atoms simultaneously. Shared variables across atoms enforce a single consistent witness, which is what makes the conjunction meaningful. Equivalently, treat the atoms as a small canonical database: the BCQ holds on an instance exactly when there is a homomorphism from that canonical database into the instance, preserving relation names, constants and repeated-variable equalities. This homomorphism view is central to query evaluation, query containment, finite-model reasoning and constraint checking. Negation, disjunction, aggregation, recursion or free output variables take a query outside the BCQ class.

Structural Signature¶

Relational signature declares relation symbols and their arities.
Finite atom conjunction requires every listed relational condition simultaneously.
Variables and constants occupy atom positions; repeated variables impose equality constraints.
Existential closure binds every variable and leaves no returned tuple.
Database instance supplies the facts against which the formula is interpreted.
Satisfying assignment or homomorphism witnesses one globally consistent match.

The signature is not merely “several conditions followed by yes or no.” The conditions must be positive relational atoms under a shared assignment. Remove existential closure and a tuple-returning conjunctive query remains; add an operator outside the fragment and a broader language results.

What It Is Not¶

A BCQ is not any SQL statement whose interface happens to display a Boolean. SQL can contain negation, grouping, arithmetic, null semantics, subqueries, and procedural features beyond the conjunctive-query fragment.

It is not a propositional conjunction of already evaluated truth values. Variables range over a database domain, atoms are interpreted through stored relations, and existential witnesses connect the atoms.

It is not a non-Boolean conjunctive query. A query such as q(x) :- Father(Mark,x), Employed(x) returns every matching x; closing x existentially asks only whether at least one exists. It is also not query containment, although homomorphisms help characterize containment between conjunctive queries.

Scope of Application¶

BCQs provide a clean core for relational query theory, finite model theory, knowledge bases, data exchange, ontology-mediated querying, integrity-constraint violation tests, and pattern existence checks. A database system may compile the query into joins and projections, while the formal identity remains the closed conjunction rather than a particular execution plan.

Complexity statements must declare the input regime. In data complexity, the query is fixed and only the database varies. In combined complexity, both query and data vary. A result from one regime cannot be copied into the other without qualification. Set semantics also matter: the logical truth test does not count duplicate witnesses.

Clarity¶

A clear BCQ specification names the schema, writes every atom, marks constants, identifies repeated variables, and states that all variables are existentially bound. It also declares whether built-in equality or constants are allowed in the chosen formalism.

The decisive evidence is a complete assignment, not a list of plausible local matches. When a query is false, a useful explanation identifies the join or relational condition that prevents any global witness.

Manages Complexity¶

The abstraction compresses a potentially large search into a small pattern: find one structure-preserving match of this relational template. The homomorphism view unifies formulas, joins, canonical databases, and containment reasoning without tying the identity to SQL syntax or one storage engine.

That compression hides multiplicity, output tuples, cost models, indexing, and evaluation strategy. These belong to implementation or neighboring query classes. Keeping syntax, semantic instance, and witness distinct prevents an optimizer's plan from being mistaken for the query itself.

Abstract Reasoning¶

Declare the relational signature and check every atom's arity.
Inventory variables and constants; verify that no variable remains free.
Build the shared constraint pattern created by repeated variables.
Search for one assignment that maps every atom to a fact in the instance.
Equivalently, test for a homomorphism from the query's canonical database.
Return true if a witness exists and false otherwise.
Before importing a theorem or complexity result, state whether the query, schema, and instance are fixed or varying.

Knowledge Transfer¶

The definition transfers literally across relational systems and logical notations when the same positive existential atom structure is preserved. Datalog syntax, first-order notation, and a join-based implementation can represent the same BCQ.

Transfer stops at resemblance. A graph-pattern language with optional edges, negated conditions, path recursion, or returned bindings may contain a conjunctive core but is not wholly a BCQ. The node remains a workspace root because no live formal-query genus has been verified; conjunction, relation, and truth participate without individually subsuming the identity.

Examples¶

Canonical¶

∃x (Father(Mark,x) ∧ Employed(x)) is evaluated on stored family and employment facts. If Ava is recorded as Mark's child and as employed, mapping x to Ava satisfies both atoms, so the query is true.

Mapped back: signature → Father/2, Employed/1; conjunction → both facts; terms → Mark and shared x; closure → x existential; instance → stored rows; witness → Ava.

Applied / In Practice¶

A compliance check asks whether some purchase is made by a customer whose address belongs to a restricted region. The query joins Purchase, Customer, and Region atoms and returns only whether a linked pattern exists. Reporting the matching purchase would require output variables and would therefore be a related non-Boolean query.

Mapped back: pattern → three relations; shared variables → customer and region identifiers; closure → all identifiers hidden; evidence → one end-to-end linked assignment.

Structural Tensions¶

Local matches versus global consistency. Each atom may match somewhere while no one assignment respects all shared variables. Diagnostic: Do repeated variables retain the same value across the full conjunction?

Boolean output versus restricted syntax. A yes/no answer can be computed by languages much richer than BCQs. Diagnostic: Is “Boolean” describing result arity, or has it been mistaken for permission to use arbitrary Boolean connectives?

Fixed pattern versus combined input. A small fixed query over growing data presents a different computational regime from a growing query and database. Diagnostic: Which objects contribute to input size?

Structural–Framed Character¶

Boolean Conjunctive Query is strongly structural: atom types, variable sharing, closure, and satisfaction can be checked formally. Its framed component lies in relational vocabulary, schema conventions, finite-instance assumptions, and the selected query language.

The abstraction is descriptive rather than evaluative. Its output is a logical judgment relative to an instance. Portability is high among relational and finite-model settings, but metaphorical “pattern matching” outside those typed semantics is not literal transfer.

Structural Core vs. Domain Accent¶

The structural core is an existentially closed conjunction with one joint witness. Database theory adds relation symbols, arities, instances, canonical databases, and query-complexity regimes.

Removing that domain accent leaves positive existential satisfaction, but no current live node captures the exact genus needed for a defensible edge. Removing closure changes the output contract; adding negation or disjunction changes expressive resources; allowing inconsistent witnesses destroys the conjunctive match.

This entry presupposes Relational Model.

Approved unparented root. No current live formal-query node is a verified necessary genus.
Conjunction participates in the query body but does not capture existential database semantics.
Relation types the atoms but does not determine the closed query.
Truth and satisfiability describe the result or semantic test, not the whole object.
Homomorphism supplies an equivalent recognition criterion in the relational setting.

Relationships to Other Abstractions¶

Current abstraction Boolean Conjunctive Query Domain-specific

Parents (1) — more general patterns this builds on

Boolean Conjunctive Query presupposes Relational Model Domain-specific

Boolean Conjunctive Query presupposes Relational Model: the parent's defining role is necessary to the child's frozen mechanism or criterion.

Hierarchy path (1) — routes to 1 parentless root

Boolean Conjunctive Query → Relational Model → Relation

Neighborhood in Abstraction Space¶

Boolean Conjunctive Query sits in a sparse region of the domain-specific corpus (87^th percentile for distinctiveness): few abstractions share its structure, so a faithful description tends to retrieve it precisely.

Family — Unclustered & Miscellaneous (2551 abstractions)

Nearest neighbors

Computed from structural-signature embeddings · 2026-10-08

Not to Be Confused With¶

Conjunctive query with outputs: exposes distinguished variables and returns tuples.
Propositional conjunction: combines truth values without relational witnesses.
General Boolean query: may use negation, disjunction, or other operators.
Query containment: compares answer inclusion between queries rather than evaluating one query on one instance.
Independent atom matches: fail when shared variables do not agree globally.

References¶

Ashok K. Chandra and Philip M. Merlin, “Optimal Implementation of Conjunctive Queries in Relational Data Bases,” STOC 1977: https://doi.org/10.1145/800105.803397
Frozen Wikipedia discovery revision: https://en.wikipedia.org/wiki/Boolean_conjunctive_query

The frozen article supports the basic syntax and example. The classic query-theory source supports the homomorphism framing; complexity claims remain explicitly qualified by input regime.