Fix #449: [Model] ConjunctiveBooleanQuery by GiggleLiu · Pull Request #689 · CodingThrust/problem-reductions

GiggleLiu · 2026-03-17T01:48:37Z

Summary

Add the Conjunctive Boolean Query (CBQ) problem model — a classical NP-complete satisfaction problem from database theory (Garey & Johnson A4 SR31). Given a finite domain, relations, and an existentially quantified conjunctive query, determine whether the query is satisfiable.

Fixes #449

codecov · 2026-03-17T01:50:19Z

Codecov Report

❌ Patch coverage is 98.04878% with 4 lines in your changes missing coverage. Please review.
✅ Project coverage is 97.36%. Comparing base (bc9d172) to head (0c77af2).
⚠️ Report is 1 commits behind head on main.

Files with missing lines	Patch %	Lines
src/models/misc/conjunctive_boolean_query.rs	96.52%	4 Missing ⚠️

Additional details and impacted files

@@            Coverage Diff             @@
##             main     #689      +/-   ##
==========================================
+ Coverage   97.34%   97.36%   +0.01%     
==========================================
  Files         331      333       +2     
  Lines       42556    42760     +204     
==========================================
+ Hits        41428    41634     +206     
+ Misses       1128     1126       -2

☔ View full report in Codecov by Sentry.
📢 Have feedback on the report? Share it here.

🚀 New features to boost your workflow:

❄️ Test Analytics: Detect flaky tests, report on failures, and find test suite problems.

Co-Authored-By: Claude Opus 4.6 <[email protected]>

…is1998

GiggleLiu · 2026-03-17T02:52:47Z

Implementation Summary

Changes

src/models/misc/conjunctive_boolean_query.rs — New model file with Relation, QueryArg, ConjunctiveBooleanQuery types, Problem/SatisfactionProblem trait impls, declare_variants!, ProblemSchemaEntry, and example-db spec
src/unit_tests/models/misc/conjunctive_boolean_query.rs — 9 unit tests (basic, evaluate yes/no, out-of-range, wrong-length, brute-force, unsatisfiable, serialization, paper example)
src/models/misc/mod.rs — Module registration and example-db chain
src/models/mod.rs, src/lib.rs — Re-exports
problemreductions-cli/src/cli.rs — New flags: --domain-size, --relations, --conjuncts-spec
problemreductions-cli/src/commands/create.rs — Full pred create ConjunctiveBooleanQuery support with relation/conjunct parsing
src/example_db/fixtures/examples.json — Regenerated with CBQ example
docs/paper/reductions.typ — Problem definition entry with data-driven example
docs/paper/references.bib — Added Chandra & Merlin 1977, Gottlob et al. 2002, Kolaitis & Vardi 1998

Deviations from Plan

None

Open Questions

None

Copilot

Pull request overview

Adds a new Conjunctive Boolean Query (CBQ) satisfaction problem model to the misc model set, including CLI instance construction support, example-db fixtures, tests, and paper documentation updates.

Changes:

Introduces ConjunctiveBooleanQuery model (+ schema registration, variants, example-db spec, and tests).
Extends pred create to construct CBQ instances from --domain-size, --relations, and --conjuncts-spec.
Updates example-db fixtures and the paper (definition section + references) to include CBQ.

Reviewed changes

Copilot reviewed 10 out of 10 changed files in this pull request and generated 4 comments.

Show a summary per file

File	Description
src/models/misc/conjunctive_boolean_query.rs	New CBQ model type, schema entry, evaluation logic, variants, and example-db builder.
src/models/misc/mod.rs	Wires CBQ module + re-exports (including `CbqRelation`, `QueryArg`) and example-db specs.
src/models/mod.rs	Re-exports CBQ types at the top-level `models` module.
src/lib.rs	Exposes CBQ types in the public prelude.
src/unit_tests/models/misc/conjunctive_boolean_query.rs	Adds unit tests for evaluation, brute-force solving, and serialization.
problemreductions-cli/src/cli.rs	Adds `pred create` flags for CBQ.
problemreductions-cli/src/commands/create.rs	Implements CBQ parsing/creation in the CLI.
src/example_db/fixtures/examples.json	Adds a canonical CBQ model fixture entry (and includes an unrelated witness tweak).
docs/paper/reductions.typ	Adds CBQ definition section with a worked example loaded from fixtures.
docs/paper/references.bib	Adds CBQ-related references (Chandra & Merlin, Gottlob et al., Kolaitis & Vardi).

💡 Add Copilot custom instructions for smarter, more guided reviews. Learn how to get started.

docs/paper/references.bib

+@article{chandra1977,
+  author  = {Ashok K. Chandra and Philip M. Merlin},
+  title   = {Optimal Implementation of Conjunctive Queries in Relational Data Bases},
+  journal = {Proceedings of the 9th Annual ACM Symposium on Theory of Computing (STOC)},
+  pages   = {77--90},
+  year    = {1977},
+  doi     = {10.1145/800105.803397}
+}
+
+@article{gottlob2002,
+  author  = {Georg Gottlob and Nicola Leone and Francesco Scarcello},
+  title   = {Hypertree Decompositions and Tractable Queries},
+  journal = {Journal of Computer and System Sciences},
+  volume  = {64},
+  number  = {3},
+  pages   = {579--627},
+  year    = {2002},
+  doi     = {10.1006/jcss.2001.1809}
+}
+
+@incollection{kolaitis1998,
+  author    = {Phokion G. Kolaitis and Moshe Y. Vardi},
+  title     = {Conjunctive-Query Containment and Constraint Satisfaction},
+  booktitle = {Proceedings of the 17th ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems (PODS)},
+  pages     = {205--213},
+  year      = {1998},
+  doi       = {10.1145/275487.275511}
+}


problemreductions-cli/src/commands/create.rs

+            // Parse relations: "arity:t1,t2|t3,t4;arity:t5,t6,t7|t8,t9,t10"
+            let relations: Vec<CbqRelation> = relations_str
+                .split(';')
+                .map(|rel_str| {
+                    let rel_str = rel_str.trim();
+                    let (arity_str, tuples_str) = rel_str.split_once(':').ok_or_else(|| {
+                        anyhow::anyhow!(
+                            "Invalid relation format: expected 'arity:tuples', got '{rel_str}'"
+                        )
+                    })?;
+                    let arity: usize = arity_str
+                        .trim()
+                        .parse()
+                        .map_err(|e| anyhow::anyhow!("Invalid arity '{arity_str}': {e}"))?;
+                    let tuples: Vec<Vec<usize>> = tuples_str
+                        .split('|')
+                        .map(|t| {
+                            t.trim()
+                                .split(',')
+                                .map(|v| {
+                                    v.trim()
+                                        .parse::<usize>()
+                                        .map_err(|e| anyhow::anyhow!("Invalid tuple value: {e}"))
+                                })
+                                .collect::<Result<Vec<_>>>()
+                        })
+                        .collect::<Result<Vec<_>>>()?;
+                    Ok(CbqRelation { arity, tuples })
+                })
+                .collect::<Result<Vec<_>>>()?;
+            // Parse conjuncts: "rel_idx:arg1,arg2;rel_idx:arg1,arg2,arg3"
+            let mut num_vars_inferred: usize = 0;
+            let conjuncts: Vec<(usize, Vec<QueryArg>)> = conjuncts_str
+                .split(';')
+                .map(|conj_str| {
+                    let conj_str = conj_str.trim();
+                    let (idx_str, args_str) = conj_str.split_once(':').ok_or_else(|| {
+                        anyhow::anyhow!(
+                            "Invalid conjunct format: expected 'rel_idx:args', got '{conj_str}'"
+                        )
+                    })?;
+                    let rel_idx: usize = idx_str.trim().parse().map_err(|e| {
+                        anyhow::anyhow!("Invalid relation index '{idx_str}': {e}")
+                    })?;
+                    let query_args: Vec<QueryArg> = args_str
+                        .split(',')
+                        .map(|a| {
+                            let a = a.trim();
+                            if let Some(rest) = a.strip_prefix('v') {
+                                let v: usize = rest.parse().map_err(|e| {
+                                    anyhow::anyhow!("Invalid variable index '{rest}': {e}")
+                                })?;
+                                if v + 1 > num_vars_inferred {
+                                    num_vars_inferred = v + 1;
+                                }
+                                Ok(QueryArg::Variable(v))
+                            } else if let Some(rest) = a.strip_prefix('c') {
+                                let c: usize = rest.parse().map_err(|e| {
+                                    anyhow::anyhow!("Invalid constant value '{rest}': {e}")
+                                })?;
+                                Ok(QueryArg::Constant(c))
+                            } else {
+                                Err(anyhow::anyhow!(
+                                    "Invalid query arg '{a}': expected vN (variable) or cN (constant)"
+                                ))
+                            }
+                        })
+                        .collect::<Result<Vec<_>>>()?;
+                    Ok((rel_idx, query_args))
+                })
+                .collect::<Result<Vec<_>>>()?;
+            (
+                ser(ConjunctiveBooleanQuery::new(
+                    domain_size,
+                    relations,
+                    num_vars_inferred,
+                    conjuncts,
+                ))?,


problemreductions-cli/src/commands/create.rs

+                    let tuples: Vec<Vec<usize>> = tuples_str
+                        .split('|')
+                        .map(|t| {
+                            t.trim()
+                                .split(',')
+                                .map(|v| {
+                                    v.trim()
+                                        .parse::<usize>()
+                                        .map_err(|e| anyhow::anyhow!("Invalid tuple value: {e}"))
+                                })
+                                .collect::<Result<Vec<_>>>()
+                        })
+                        .collect::<Result<Vec<_>>>()?;


src/models/misc/conjunctive_boolean_query.rs

+            let tuple: Vec<usize> = args
+                .iter()
+                .map(|arg| match arg {
+                    QueryArg::Variable(i) => config[*i],
+                    QueryArg::Constant(c) => *c,
+                })
+                .collect();
+            self.relations[*rel_idx].tuples.contains(&tuple)


GiggleLiu · 2026-03-18T20:20:48Z

Agentic Review Report

Structural Check

#	Check	Status
1	Model file exists (`src/models/misc/conjunctive_boolean_query.rs`)	✅ PASS
2	`inventory::submit!` present	✅ PASS
3	`#[derive(...Serialize, Deserialize)]` on struct	✅ PASS
4	`Problem` trait impl	✅ PASS
5	`SatisfactionProblem` impl	✅ PASS
6	`#[cfg(test)]` + `#[path]` test link	✅ PASS
7	Test file exists (9 test functions)	✅ PASS
8	Registered in `misc/mod.rs`	✅ PASS
9	Re-exported in `models/mod.rs` + `lib.rs` prelude	✅ PASS
10	`declare_variants!` entry	✅ PASS
11	CLI alias `CBQ` registered	✅ PASS
12	CLI `create` support with flags	✅ PASS
13	Canonical model example registered	✅ PASS
14	Paper `display-name` entry	✅ PASS
15	Paper `problem-def` block	✅ PASS

Build: make test ✅ | make clippy ✅ | make fmt-check ✅

Semantic Review:

evaluate(): Correctly validates config length/domain bounds, resolves Variable/Constant arguments, checks all conjuncts via tuple membership — matches the CBQ definition.
dims(): Returns vec![domain_size; num_variables] — correct.
Complexity string "domain_size ^ num_variables": Appropriate brute-force bound (|D|^l). No substantially faster general algorithm is known.
Input validation in new(): Comprehensive — checks arities, domain bounds, relation indices, argument counts, variable/constant ranges.
Edge cases: evaluate returns false for wrong-length or out-of-range configs. Empty-conjunct case is vacuously true (correct).
Paper: Well-written with data-driven example, proper citations (Chandra & Merlin 1977, Kolaitis & Vardi 1998, Gottlob et al. 2002).

Issue Compliance (#449): 10/10 checks passed — name, definition, type (satisfaction), schema, getters, complexity, and example all match.

Whitelist Note: Deterministic whitelist check failed due to a minor unrelated change in examples.json — the KSatisfiability/KN → Satisfiability solution changed from [1,1,1,0] to [1,1,1,1]. Both are valid satisfying assignments; this is a benign fixture regeneration artifact.

Quality Check

Design Principles:

DRY: OK — Test helper and canonical example both construct the same instance, which is the standard pattern in this codebase.
KISS: OK — Clean, minimal implementation. CLI parsing complexity is proportional to the encoding.
HC/LC: OK — Self-contained model file, CLI parsing in its proper place.

HCI (CLI):

Error messages: OK — Each missing flag produces actionable messages with full usage examples.
Discoverability: OK — CBQ listed in help text with required flags.
Consistency: OK — ; and : separators mirror patterns used elsewhere in the CLI.

Test Quality: 9 test functions covering creation, positive/negative evaluation, boundary conditions (out-of-range, wrong-length), solver integration (satisfiable + unsatisfiable), serialization round-trip, and exhaustive verification via find_all_satisfying. Well above the minimum of 3.

Issues Found:

#	Severity	Issue	Location
Q1	warning	Unrelated KSat fixture change in `examples.json` — solution changed from `[1,1,1,0]` to `[1,1,1,1]`. Benign (both valid) but pollutes commit scope.	`src/example_db/fixtures/examples.json`
Q2	warning	`num_variables` silently inferred from highest variable index in `--conjuncts-spec`. If user specifies `v0` and `v2` but not `v1`, `num_variables = 3` with `v1` as a free variable. Technically correct but could surprise users.	`create.rs:1595-1618`
Q3	info	`tuples.contains()` is linear-time in `evaluate()`. Fine for brute-force context.	`conjunctive_boolean_query.rs:219`

Agentic Feature Tests

#	Test	Command	Result
1	Catalog listing	`pred list`	✅ PASS — CBQ appears with alias, complexity, default variant
2a	Show (full name)	`pred show ConjunctiveBooleanQuery`	✅ PASS
2b	Show (alias)	`pred show CBQ`	✅ PASS
3	Example creation	`pred create --example CBQ`	✅ PASS — valid JSON
4	Custom creation	`pred create CBQ --domain-size 6 --relations "..." --conjuncts-spec "..."`	✅ PASS
5a	Solve (ILP)	`pred create --example CBQ \| pred solve -`	✅ PASS (expected failure) — "No reduction path"
5b	Solve (brute-force)	`pred create --example CBQ \| pred solve - --solver brute-force`	✅ PASS — returns [0, 1]
5c	Solve (unsatisfiable)	custom UNSAT instance	✅ PASS — "No solution found"
6a	Missing --relations	`pred create CBQ --domain-size 6`	✅ PASS — graceful error
6b	Invalid relation format	`pred create CBQ --domain-size 6 --relations "bad" ...`	✅ PASS — graceful error
6c	Out-of-range tuple values	domain_size=2, tuple entry=5	❌ FAIL — panics instead of graceful error
6d	Out-of-range relation index	conjunct references relation 5 (only 1 exists)	❌ FAIL — panics instead of graceful error
6e	Missing --domain-size	`pred create CBQ --relations "..." --conjuncts-spec "..."`	✅ PASS — graceful error
6f	Missing --conjuncts-spec	`pred create CBQ --domain-size 6 --relations "..."`	✅ PASS — graceful error

11 PASS, 2 FAIL, 1 WARNING

Issues Found:

#	Severity	Issue	Location
A1	low	Out-of-range inputs cause panics instead of graceful errors. The `new()` constructor uses `assert!` which panics. The validation messages are accurate but the panic-style exit is not ideal CLI UX. This is a common pattern in this codebase (many models use `assert!` in constructors).	`conjunctive_boolean_query.rs:117,125`
A2	low	Compiler warning: unreachable `"Vec<u64>"` match arm in `type_format_hint()` — duplicate arm introduced by this PR.	`create.rs:240`

Generated by review-pipeline

Resolve conflicts: keep ConjunctiveBooleanQuery alongside newly added models (RectilinearPictureCompression, StringToStringCorrection, etc.). Adapt ModelExampleSpec to the new API (instance/optimal_config/optimal_value fields instead of build closure). Co-Authored-By: Claude Opus 4.6 (1M context) <[email protected]>

- Fix BibTeX entry types: chandra1977 @Article -> @inproceedings, kolaitis1998 @incollection -> @inproceedings - Support empty relations in CLI parsing (e.g., "2:" produces empty relation) - Pre-validate CLI input before calling ConjunctiveBooleanQuery::new(): tuple arity, domain bounds, relation indices, conjunct arity, constant bounds — returns user-facing errors instead of panicking Co-Authored-By: Claude Opus 4.6 (1M context) <[email protected]>

Co-Authored-By: Claude Opus 4.6 (1M context) <[email protected]>

Resolve conflicts: keep ConjunctiveBooleanQuery alongside newly added PartiallyOrderedKnapsack model. Co-Authored-By: Claude Opus 4.6 (1M context) <[email protected]>

zazabap · 2026-03-19T08:24:29Z

Final review notes:

Merged main, resolved conflicts (PartiallyOrderedKnapsack + RectilinearPictureCompression)
Adapted ModelExampleSpec to the new API (instance/optimal_config/optimal_value fields)
Fixed agentic review items 6c/6d: out-of-range tuple values and relation indices now return graceful CLI errors instead of panicking
Fixed BibTeX entry types (chandra1977 → @inproceedings, kolaitis1998 → @inproceedings)
Added CLI pre-validation for tuple arity, domain bounds, conjunct arity, and constant bounds
Supported empty relations in --relations parsing (e.g., "2:")
Added missing CBQ fields to empty_args test helper

All local checks pass (make check green). CI triggered.

zazabap

Final review passed. All agentic test failures (6c, 6d) fixed, BibTeX corrected, CLI validation hardened. LGTM.

Add plan for #449: [Model] ConjunctiveBooleanQuery

c3b0b19

GiggleLiu and others added 5 commits March 17, 2026 10:11

Implement ConjunctiveBooleanQuery model (#449)

e51c984

Co-Authored-By: Claude Opus 4.6 <[email protected]>

Regenerate example-db fixtures for CBQ model

c2c13bc

Add paper entry for ConjunctiveBooleanQuery (#449)

d06a1d4

Review fixes: add PartialEq derives, fix bib key kolaitis2000->kolait…

4cdbbd7

…is1998

chore: remove plan file after implementation

7d438ed

GiggleLiu requested a review from Copilot March 17, 2026 02:53

Copilot started reviewing on behalf of GiggleLiu March 17, 2026 02:53 View session

Copilot AI reviewed Mar 17, 2026

View reviewed changes

zazabap and others added 4 commits March 19, 2026 07:56

fix: add missing CBQ fields to empty_args test helper

3ee4efc

Co-Authored-By: Claude Opus 4.6 (1M context) <[email protected]>

Merge origin/main into issue-449-conjunctive-boolean-query

0c77af2

Resolve conflicts: keep ConjunctiveBooleanQuery alongside newly added PartiallyOrderedKnapsack model. Co-Authored-By: Claude Opus 4.6 (1M context) <[email protected]>

zazabap approved these changes Mar 19, 2026

View reviewed changes

zazabap merged commit 5a255c4 into main Mar 19, 2026
5 checks passed

GiggleLiu deleted the issue-449-conjunctive-boolean-query branch April 12, 2026 00:53

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Fix #449: [Model] ConjunctiveBooleanQuery#689

Fix #449: [Model] ConjunctiveBooleanQuery#689
zazabap merged 10 commits intomainfrom
issue-449-conjunctive-boolean-query

GiggleLiu commented Mar 17, 2026

Uh oh!

codecov bot commented Mar 17, 2026 •

edited

Loading

Uh oh!

GiggleLiu commented Mar 17, 2026

Uh oh!

Copilot AI left a comment

Uh oh!

GiggleLiu commented Mar 18, 2026

Uh oh!

zazabap commented Mar 19, 2026

Uh oh!

zazabap left a comment

Uh oh!

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

3 participants

Conversation

GiggleLiu commented Mar 17, 2026

Summary

Uh oh!

codecov bot commented Mar 17, 2026 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Codecov Report

Uh oh!

GiggleLiu commented Mar 17, 2026

Implementation Summary

Changes

Deviations from Plan

Open Questions

Uh oh!

Copilot AI left a comment

Choose a reason for hiding this comment

Pull request overview

Reviewed changes

Uh oh!

GiggleLiu commented Mar 18, 2026

Agentic Review Report

Structural Check

Quality Check

Agentic Feature Tests

Uh oh!

zazabap commented Mar 19, 2026

Uh oh!

zazabap left a comment

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

3 participants

codecov bot commented Mar 17, 2026 •

edited

Loading