Fix #447: [Model] BoyceCoddNormalFormViolation by GiggleLiu · Pull Request #685 · CodingThrust/problem-reductions

GiggleLiu · 2026-03-16T19:13:37Z

Summary

Add the BoyceCoddNormalFormViolation satisfaction problem model (Garey & Johnson A4 SR29). Given attributes, functional dependencies, and a target subset, determines whether the subset violates Boyce-Codd Normal Form.

Fixes #447

codecov · 2026-03-16T19:37:07Z

Codecov Report

✅ All modified and coverable lines are covered by tests.
✅ Project coverage is 97.42%. Comparing base (482c75a) to head (dfa26f7).
⚠️ Report is 1 commits behind head on main.

Additional details and impacted files

@@           Coverage Diff            @@
##             main     #685    +/-   ##
========================================
  Coverage   97.42%   97.42%            
========================================
  Files         347      349     +2     
  Lines       44459    44686   +227     
========================================
+ Hits        43315    43537   +222     
- Misses       1144     1149     +5

☔ 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.

Add the Boyce-Codd Normal Form Violation satisfaction problem model (Garey & Johnson A4 SR29). Given attributes, functional dependencies, and a target subset, determines whether a BCNF violation exists. - Model: src/models/misc/boyce_codd_normal_form_violation.rs - Tests: 20 unit tests covering evaluation, solver, serialization, edge cases - CLI: create support with --n, --sets (lhs:rhs format), --target - Paper: problem-def entry in docs/paper/reductions.typ - Example-db: canonical example with violation witness X={2}

GiggleLiu · 2026-03-16T19:49:04Z

Implementation Summary

Changes

src/models/misc/boyce_codd_normal_form_violation.rs — New satisfaction problem model with struct, constructor validation, closure computation, evaluate(), declare_variants!
src/unit_tests/models/misc/boyce_codd_normal_form_violation.rs — 20 unit tests: creation, evaluation (violation/non-violation/cyclic-keys/multi-step/out-of-target FDs), solver, serialization, constructor panics, normalization
src/models/misc/mod.rs — Module registration
problemreductions-cli/src/commands/create.rs — CLI create support with --n, --sets (FD format: lhs:rhs;...), --target
docs/paper/reductions.typ — Display name + problem-def entry
src/example_db/fixtures/examples.json — Regenerated with canonical BCNF example

Deviations from Plan

None

Open Questions

None

Copilot

Pull request overview

Adds a new satisfaction problem model for Boyce–Codd Normal Form Violation (G&J A4 SR29) and wires it into the library, CLI instance creation, example database fixtures, and the reductions paper.

Changes:

Introduces BoyceCoddNormalFormViolation model with schema registration, variant declaration, and example-db spec.
Adds comprehensive unit tests covering evaluation behavior, validation, solver integration, and serialization.
Integrates the model into the CLI pred create flow and the curated example fixtures/docs.

Reviewed changes

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

Show a summary per file

File	Description
`src/models/misc/boyce_codd_normal_form_violation.rs`	New model implementation + schema registration + variants + example-db spec + test module hook
`src/models/misc/mod.rs`	Exposes the new model and includes its canonical example spec
`problemreductions-cli/src/commands/create.rs`	Adds CLI construction/parsing for `BoyceCoddNormalFormViolation`
`src/unit_tests/models/misc/boyce_codd_normal_form_violation.rs`	Unit tests for correctness, validation, solver behavior, and serde roundtrip
`src/example_db/fixtures/examples.json`	Adds canonical model example fixture entry (samples + satisfying solutions)
`docs/paper/reductions.typ`	Adds name mapping and formal problem definition to the paper

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

docs/paper/reductions.typ

+#problem-def("BoyceCoddNormalFormViolation")[
+  *Instance:* A set $A$ of attribute names, a collection $F$ of functional dependencies on $A$, and a subset $A' subset.eq A$.
+
+  *Question:* Is there a subset $X subset.eq A'$ and two attributes $y, z in A' without X$ such that $y in X^+$ but $z in.not X^+$, where $X^+$ is the closure of $X$ under $F$?


src/models/misc/mod.rs

 mod subset_sum;

 pub use bin_packing::BinPacking;
+pub use boyce_codd_normal_form_violation::BoyceCoddNormalFormViolation;


problemreductions-cli/src/commands/create.rs

+            let fds: Vec<(Vec<usize>, Vec<usize>)> = sets_str
+                .split(';')
+                .map(|fd_str| {
+                    let parts: Vec<&str> = fd_str.split(':').collect();
+                    anyhow::ensure!(
+                        parts.len() == 2,
+                        "Each FD must be lhs:rhs, got '{}'",
+                        fd_str
+                    );
+                    let lhs: Vec<usize> = util::parse_comma_list(parts[0])?;
+                    let rhs: Vec<usize> = util::parse_comma_list(parts[1])?;
+                    Ok((lhs, rhs))
+                })
+                .collect::<Result<_>>()?;
+            let target: Vec<usize> = util::parse_comma_list(target_str)?;
+            (
+                ser(BoyceCoddNormalFormViolation::new(n, fds, target))?,
+                resolved_variant.clone(),
+            )


src/models/misc/boyce_codd_normal_form_violation.rs

+    /// Create a new Boyce-Codd Normal Form Violation instance.
+    ///
+    /// # Panics
+    ///
+    /// Panics if any attribute index in `functional_deps` or `target_subset` is
+    /// out of range (≥ `num_attributes`), if `target_subset` is empty, or if any
+    /// functional dependency has an empty LHS.
+    pub fn new(
+        num_attributes: usize,
+        functional_deps: Vec<(Vec<usize>, Vec<usize>)>,
+        target_subset: Vec<usize>,
+    ) -> Self {


GiggleLiu · 2026-03-18T18:22:11Z

Agentic Review Report

Structural Check

#	Check	Status
1	Model file exists (`src/models/misc/boyce_codd_normal_form_violation.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	PASS
8	Test file has >= 3 test functions	PASS — 20 test functions
9	Registered in `misc/mod.rs`	PASS
10	Re-exported in `models/mod.rs`	FAIL — `BoyceCoddNormalFormViolation` missing from `pub use misc::{...}` in `src/models/mod.rs` (line 23-27). All other misc models are listed there.
11	`declare_variants!` entry exists	PASS
12	CLI alias resolution	PASS — aliases `BCNFViolation`, `BCNF`
13	CLI `create` support	PASS
14	Canonical model example registered	PASS
15	Paper `display-name` entry	PASS
16	Paper `problem-def` block	PASS

Semantic Review:

evaluate() correctness: OK — correctly builds X from config, computes attribute closure via fixed-point, checks BCNF violation condition (∃ y∈X⁺∩(A'\X), ∃ z∉X⁺∩(A'\X))
dims() correctness: OK — vec![2; target_subset.len()]
Constructor validation: OK — rejects empty target_subset, empty FD LHS, out-of-range indices; normalizes by sorting/dedup
Paper entry: OK — matches G&J A4 SR29 definition, cites Beeri & Bernstein (1979)

Issue Compliance: 8/8 checks passed

Findings:

FAIL (structural Design Decision: Type-erased names in ReductionGraph topology #10): BoyceCoddNormalFormViolation not re-exported in src/models/mod.rs. The prelude in src/lib.rs works correctly, so this is a consistency gap rather than build-breaking.
Minor: Complexity string "2^num_target_attributes * num_target_attributes^2 * num_functional_deps" uses num_target_attributes^2 for closure cost, but the closure can visit num_attributes (which may exceed num_target_attributes). More precise: num_attributes^2. Equivalent when A'=A.

Quality Check

Design Principles:

DRY: OK — ensure_attribute_indices_in_range helper properly extracts repeated validation; no duplication
KISS: OK — straightforward struct + fixed-point closure + two-flag check; no over-engineering
HC/LC: OK — model file self-contained; CLI block follows existing patterns

HCI (CLI changed):

Error messages: OK — full usage lines with concrete examples in every error path
Discoverability: OK — example_for function provides canonical example
Consistency: OK — reuses --n, --sets, --target flags
Feedback: OK — validates all inputs before construction

Test Quality:

20 unit tests covering: value verification, adversarial/boundary cases (empty X, full X, invalid configs), non-trivial instances (6 attrs, cyclic keys), constructor validation (4 #[should_panic] tests), normalization, multi-step transitive closure
3 CLI tests for index bounds validation
1 integration test for prelude accessibility
Assert density appropriate throughout

Findings:

Minor: Complexity string uses num_target_attributes^2 where num_attributes^2 would be more precise for closure computation (src/models/misc/boyce_codd_normal_form_violation.rs:219)
Minor: --sets flag semantically overloaded for functional dependencies vs set collections (problemreductions-cli/src/commands/create.rs:930). Follows existing codebase pattern; error messages document expected format.

Agentic Feature Tests

#	Test	Command	Result
1	Model in catalog	`pred list`	PASS
2	Details display	`pred show BoyceCoddNormalFormViolation`	PASS
3	Alias (BCNF)	`pred show BCNF`	PASS
4	Alias (BCNFViolation)	`pred show BCNFViolation`	PASS
5	Example creation	`pred create --example BoyceCoddNormalFormViolation`	PASS
6	Solve (satisfiable)	`pred solve --solver brute-force`	PASS — returns valid BCNF violation witness
7	Solve (unsatisfiable)	`pred solve --solver brute-force` on trivial instance	PASS — "No solution found"
8	Schema-driven create	`pred create BoyceCoddNormalFormViolation --n 6 --sets "..." --target ...`	PASS
9	Unit tests	`cargo test -- boyce`	PASS — 20/20
10	Doc tests	`cargo test` (doc-tests)	PASS
11	Full test suite	`cargo test`	PASS — 2271 tests, 0 failures
12	Clippy	`cargo clippy --all-targets`	PASS
13	Formatting	`cargo fmt -- --check`	PASS

Findings:

Confirmed (low): Duplicate Vec<u64> match arm in problemreductions-cli/src/commands/create.rs (line 251 duplicates line 244) — produces unreachable_patterns compiler warning. Recommended fix: remove duplicate arm.
Confirmed (low): BoyceCoddNormalFormViolation not listed in pred create --help flags-by-problem table. Schema-driven fallback works correctly. Cosmetic omission.

Generated by review-pipeline

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

Add plan for #447: [Model] BoyceCoddNormalFormViolation

ced1053

GiggleLiu added 2 commits March 17, 2026 03:48

chore: remove plan file after implementation

41b8d23

GiggleLiu requested a review from Copilot March 16, 2026 19:49

Copilot started reviewing on behalf of GiggleLiu March 16, 2026 19:50 View session

Copilot AI reviewed Mar 16, 2026

View reviewed changes

fix: address PR #685 review comments

ead280f

isPANN self-assigned this Mar 19, 2026

isPANN and others added 2 commits March 20, 2026 00:58

resolve merge conflicts after merging main

324d71c

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

fix: update BCNF canonical example spec to new ModelExampleSpec API

004bfc0

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

isPANN approved these changes Mar 19, 2026

View reviewed changes

isPANN mentioned this pull request Mar 19, 2026

[Model] BoyceCoddNormalFormViolation #447

Closed

3 tasks

Merge branch 'main' into issue-447-boycecnoddnormalformviolation

dfa26f7

isPANN merged commit 90f8733 into main Mar 19, 2026
3 checks passed

GiggleLiu deleted the issue-447-boycecnoddnormalformviolation branch April 12, 2026 00:53

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Fix #447: [Model] BoyceCoddNormalFormViolation#685

Fix #447: [Model] BoyceCoddNormalFormViolation#685
isPANN merged 7 commits intomainfrom
issue-447-boycecnoddnormalformviolation

GiggleLiu commented Mar 16, 2026

Uh oh!

codecov bot commented Mar 16, 2026 •

edited

Loading

Uh oh!

GiggleLiu commented Mar 16, 2026

Uh oh!

Copilot AI left a comment

Uh oh!

GiggleLiu commented Mar 18, 2026

Uh oh!

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

3 participants

Conversation

GiggleLiu commented Mar 16, 2026

Summary

Uh oh!

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

Uh oh!

Codecov Report

Uh oh!

GiggleLiu commented Mar 16, 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!

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

3 participants

codecov bot commented Mar 16, 2026 •

edited

Loading