[Model] ConjunctiveBooleanQuery

[isPANN]

Motivation

CONJUNCTIVE BOOLEAN QUERY (P179) from Garey & Johnson, A4 SR31. A classical NP-complete problem in database theory. Evaluating a conjunctive Boolean query over a relational database asks whether a given existentially quantified conjunction of relational atoms is true. This is the most basic query evaluation problem in databases and is equivalent to the constraint satisfaction problem and the graph homomorphism problem.

Associated reduction rules:

• R125: Clique -> Conjunctive Boolean Query (this problem is the target)

Definition

Name: ConjunctiveBooleanQuery
Canonical name: Conjunctive Boolean Query (also: Boolean Conjunctive Query Evaluation, BCQ, CQ Evaluation)
Reference: Garey & Johnson, Computers and Intractability, A4 SR31

Mathematical definition:

INSTANCE: Finite domain set D, a collection R = {R_1, R_2, ..., R_m} of relations, where each R_i consists of a set of d_i-tuples with entries from D, and a conjunctive Boolean query Q over R and D, where such a query Q is of the form
(exists y_1, y_2, ..., y_l)(A_1 ∧ A_2 ∧ ... ∧ A_r)
with each A_i of the form R_j(u_1, u_2, ..., u_{d_j}) where each u in {y_1, ..., y_l} ∪ D.
QUESTION: Is Q, when interpreted as a statement about R and D, true?

The problem is a decision (satisfaction) problem: the answer is a Boolean.

Variables

• Count: l (number of existentially quantified variables y_1, ..., y_l)
• Per-variable domain: |D| (each variable can take any value from the domain D)
• dims() specification: vec![domain_size; num_variables] — l variables each with domain size |D|
• Meaning: Variable y_i is assigned a value from D. The configuration (y_1 = d_1, ..., y_l = d_l) is valid (query is true) if for every conjunct A_j = R_k(u_1, ..., u_{d_k}), the tuple obtained by substituting each y_i with d_i is present in relation R_k.

Schema (data type)

Type name: ConjunctiveBooleanQuery
Variants: none (the query and database are stored directly)

Field	Type	Description
domain_size	usize	Size of the finite domain D (elements indexed 0..domain_size)
relations	Vec<Relation>	Collection R = {R_1, ..., R_m}; each Relation has an arity and a set of tuples
num_variables	usize	Number of existentially quantified variables l
conjuncts	Vec<(usize, Vec<QueryArg>)>	Query conjuncts: each is (relation_index, arguments)

Companion types (defined in model file):

pub struct Relation {
    pub arity: usize,
    pub tuples: Vec<Vec<usize>>,  // each tuple has length == arity, entries in 0..domain_size
}

pub enum QueryArg {
    Variable(usize),   // index into existential variables 0..num_variables
    Constant(usize),   // a fixed value from domain 0..domain_size
}

Size fields (getter methods): domain_size() (= |D|), num_relations() (= m), num_variables() (= l), num_conjuncts() (= r).

Notes:

• This is a satisfaction (decision) problem: Metric = bool, implementing SatisfactionProblem.

Complexity

• Decision complexity: NP-complete (Chandra and Merlin, 1977; transformation from CLIQUE).
• Best known exact algorithm: Brute-force enumeration of all |D|^l assignments of the l variables to domain elements, checking each assignment against all r conjuncts. This runs in O(|D|^l * r * max_arity) time. No substantially faster general algorithm is known.
• Parameterized: For queries of bounded treewidth (or more generally, bounded hypertree-width), evaluation is in polynomial time (combined complexity). Specifically, acyclic conjunctive queries can be evaluated in O(|D| * |Q| * |R|) time using Yannakakis's algorithm. The problem is W[1]-hard parameterized by the number of variables.
• References:
  • [Chandra and Merlin, 1977] A. K. Chandra and P. M. Merlin, "Optimal Implementation of Conjunctive Queries in Relational Data Bases", Proc. 9th STOC, pp. 77-90, 1977.
  • [Yannakakis, 1981] M. Yannakakis, "Algorithms for Acyclic Database Schemes", Proc. VLDB, pp. 82-94, 1981.
  • [Grohe, 2007] M. Grohe, "The Complexity of Homomorphism and Constraint Satisfaction Problems Seen from the Other Side", J. ACM, 54(1), Article 1, 2007.

Specialization

• Related problems: Conjunctive Query Foldability (containment), Constraint Satisfaction Problem (CSP), Graph Homomorphism, Clique.
• Special cases: When the query is the k-clique query (k existential variables, C(k,2) binary conjuncts), the problem is exactly k-CLIQUE. When R has a single binary relation and the query is a triangle query, it is TRIANGLE DETECTION.
• Generalization: Replacing the conjunctive query by an arbitrary first-order sentence makes the problem PSPACE-complete, even for D = {0,1}.

Extra Remark

Full book text:

INSTANCE: Finite domain set D, a collection R = {R1,R2,...,Rm} of relations, where each Ri consists of a set of di-tuples with entries from D, and a conjunctive Boolean query Q over R and D, where such a query Q is of the form
(exists y1,y2,...,yl)(A1 ∧ A2 ∧ ... ∧ Ar)
with each Ai of the form Rj(u1,u2,...,udj) where each u in {y1,y2,...,yl} ∪ D.
QUESTION: Is Q, when interpreted as a statement about R and D, true?
Reference: [Chandra and Merlin, 1977]. Transformation from CLIQUE.
Comment: If we are allowed to replace the conjunctive query Q by an arbitrary first-order sentence involving the predicates in R, then the problem becomes PSPACE-complete, even for D = {0,1}.

How to solve

• It can be solved by (existing) bruteforce. Enumerate all |D|^l assignments of the l existential variables to domain values; for each assignment, check whether every conjunct A_i is satisfied (i.e., the resulting tuple is in the appropriate relation R_j).
• It can be solved by reducing to integer programming.
• Other: Can be solved by reducing to constraint satisfaction problem (CSP) formulations, or by graph homomorphism algorithms for the special case of a single binary relation.

Example Instance

Domain D = {0, 1, 2, 3, 4, 5} (6 elements)

Relations (two relations with different arities):

• R_1 (arity 2): {(0,3), (1,3), (2,4), (3,4), (4,5)}
• R_2 (arity 3): {(0,1,5), (1,2,5), (2,3,4), (0,4,3)}

Query Q (2 existential variables, 3 conjuncts, mixes variables and constants):
(exists y_1, y_2)(R_1(y_1, 3) ∧ R_1(y_2, 3) ∧ R_2(y_1, y_2, 5))

"Find two values y_1, y_2 from D such that (y_1, 3) ∈ R_1, (y_2, 3) ∈ R_1, and (y_1, y_2, 5) ∈ R_2."

2 existential variables, 3 conjuncts. Arguments include both Variable references (y_1, y_2) and Constant values (3, 5).

Answer: TRUE

Satisfying assignment: y_1 = 0, y_2 = 1

Verification:

• R_1(0, 3): (0,3) ∈ R_1 ✓
• R_1(1, 3): (1,3) ∈ R_1 ✓
• R_2(0, 1, 5): (0,1,5) ∈ R_2 ✓
  All 3 conjuncts satisfied.

Non-solution: y_1 = 1, y_2 = 2 fails because R_1(2, 3) requires (2,3) ∈ R_1, but only (2,4) is present.

Why this example is representative: Unlike a pure graph-clique encoding, this instance uses multiple relations of different arities (binary and ternary) and mixes Variable and Constant arguments in the query, exercising the full generality of the conjunctive Boolean query formulation.

[zazabap]

Issue Quality Check — Model

Check	Result	Details
Usefulness	✅ Pass	Novel problem not yet in reduction graph; associated rule R125 planned; equivalent to CSP
Non-trivial	✅ Pass	Distinct input structure (domain + relations + conjunctive query); not isomorphic to any existing problem
Correctness	✅ Pass	Chandra & Merlin (1977) and Yannakakis (1981) both verified; NP-completeness claims accurate
Well-written	✅ Pass	All sections present and substantive; clear example with full verification

Overall: 4 passed, 0 failed, 0 warnings

---

Usefulness

The problem ConjunctiveBooleanQuery does not exist in the current codebase. The motivation is excellent: this is the most basic query evaluation problem in databases, equivalent to the constraint satisfaction problem (CSP) and the graph homomorphism problem. It connects to existing problems via reduction from CLIQUE (R125). Two solver methods are identified (brute-force and CSP reduction).

Non-trivial

The input structure (finite domain, relations, existentially quantified conjunctive query) is genuinely distinct from all existing problems. While related to ConjunctiveQueryFoldability (issue #448), this is a fundamentally different problem: evaluation (is Q true?) vs containment (can Q_1 be folded into Q_2?). The problem has different feasibility constraints and a different computational structure.

Correctness

• Chandra & Merlin (1977): Verified. "Optimal Implementation of Conjunctive Queries in Relational Data Bases", Proc. 9th STOC, pp. 77-90. The paper establishes NP-completeness of conjunctive query evaluation. The citation is accurate.
• Yannakakis (1981): Verified. "Algorithms for Acyclic Database Schemes", Proc. VLDB, pp. 82-94, 1981. The paper provides polynomial-time algorithms for acyclic conjunctive queries, consistent with the issue's claims about parameterized complexity.
• G&J reference (A4 SR31): Consistent. NP-completeness is via transformation from CLIQUE, as stated.
• Complexity bound: The brute-force O(|D|^l * r * max_arity) is correct.

Well-written

All required sections are present and substantive:

• Motivation: Concrete use case with clear connections to CSP and graph homomorphism.
• Name: ConjunctiveBooleanQuery -- satisfaction problem, no prefix needed. Follows conventions.
• Definition: Formal INSTANCE/QUESTION format from G&J, mathematically well-formed.
• Variables: Clean and clear: l variables with domain |D|, each representing an assignment to an existential variable.
• Schema: Well-designed with QueryArg enum for arguments. The domain_size: usize field is appropriate.
• Complexity: Well-researched with three references covering general, acyclic, and parameterized cases.
• Example: Excellent -- a 4-clique query on a 7-vertex graph with full verification of the satisfying assignment. Also notes that the 5-clique query would be FALSE, providing implicit negative instance coverage.

Recommendations

• The QueryArg type referenced in the schema (Variable vs Constant) should be explicitly defined as a Rust enum in the implementation. This is already implicit in the schema but could be made more explicit in the issue.
• Consider noting that this problem is a special case of the general CSP, which may enable future reductions in both directions.

[isPANN]

Fix-issue changelog

• Replaced trivial 4-clique example with a multi-relation example: 2 relations of different arities (binary + ternary), mixes Variable and Constant arguments in the query
• Added dims() specification to Variables section: vec![domain_size; num_variables]
• Added Size fields (getter methods) to Schema section: domain_size(), num_relations(), num_variables(), num_conjuncts()
• Replaced Vec<Vec<Vec<usize>>> for relations with Vec<Relation> using companion Relation struct (with explicit arity field)
• Added companion type definitions for Relation and QueryArg enums
• Added Notes section (satisfaction problem, Metric = bool)

Applied by /fix-issue.