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 is a closed positive existential formula made from a finite conjunction of relational atoms. It returns true exactly when one assignment of database values satisfies every atom together. With Father(parent,child) and Employed(person), ∃x(Father(Mark,x) ∧ Employed(x)) asks whether one person is both Mark's child and employed.

“Boolean” describes the yes/no result, not permission to use arbitrary Boolean connectives. Negation, disjunction, aggregation, recursion, or a free output variable moves the query into another class. A satisfying assignment can equivalently be understood as a homomorphism from the query's canonical database into the target instance.

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.

Scope of Application¶

BCQs provide a precise existence test across relational and logical settings:

Relational databases — Ask whether a join pattern has at least one witness.
Finite model theory — Interpret positive existential sentences over finite structures.
Knowledge bases — Test whether asserted facts jointly realize a requested pattern.
Data exchange — Express existence conditions over source or target instances.
Constraint checking — Detect a forbidden or required relational configuration.

Logical, Datalog, and join notation can preserve one identity. Complexity claims must still state whether only data varies or query and data both count as input; multiple witnesses do not change the Boolean result.

Clarity¶

A complete specification names the schema, relation arities, constants, repeated variables, and existential closure. The decisive evidence is one globally consistent witness. Separate matches for individual atoms fail when they assign different values to a shared variable.

Distinguish the BCQ from a conjunctive query that returns matching tuples, from a general SQL query that happens to emit a Boolean, and from query containment, which compares two queries rather than evaluating one on one instance.

Manages Complexity¶

The abstraction compresses a potentially large search into one structural question: does this relational pattern map consistently into the instance? The homomorphism view unifies formulas, joins, canonical databases, and containment reasoning while leaving storage and execution plans outside the identity.

Abstract Reasoning¶

Declare the relational signature and verify every atom's arity. Inventory variables and constants, bind every variable existentially, and record equality constraints created by repeated variables. Search for one assignment—or homomorphism—that sends all atoms to facts while preserving constants and shared values. Return true only when the full pattern is satisfied. Before importing results, state the precise fragment and complexity regime.

Knowledge Transfer¶

The definition transfers among relational systems when positive existential atom structure is preserved. Graph or rule languages with optional edges, negation, returned bindings, or recursion may contain a conjunctive core but are not wholly BCQs. No immediate DAG parent is asserted because the current catalog lacks a verified formal-query genus; conjunction, relation, and truth are ingredients rather than strict parents.

Notation may change; closure and joint satisfaction may not.

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