Fix #445: [Model] AdditionalKey by GiggleLiu · Pull Request #681 · CodingThrust/problem-reductions

GiggleLiu · 2026-03-16T17:33:23Z

Summary

Add the AdditionalKey satisfaction problem model from relational database theory (Garey & Johnson A4 SR27). This NP-complete problem asks whether a relational schema has a candidate key not in a given set of known keys.

Fixes #445

codecov · 2026-03-16T17:35:49Z

Codecov Report

✅ All modified and coverable lines are covered by tests.
✅ Project coverage is 97.45%. Comparing base (90f8733) to head (8ca70f0).
⚠️ Report is 1 commits behind head on main.

Additional details and impacted files

@@            Coverage Diff             @@
##             main     #681      +/-   ##
==========================================
+ Coverage   97.42%   97.45%   +0.02%     
==========================================
  Files         349      351       +2     
  Lines       44686    44931     +245     
==========================================
+ Hits        43537    43788     +251     
+ Misses       1149     1143       -6

☔ 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 Additional Key problem from relational database theory (Garey & Johnson SR7). Given a relational schema (R, F) and known candidate keys K, determines whether R has a candidate key not in K. - Model file with closure computation, minimality check, and known-key filter - 13 unit tests covering creation, evaluation, edge cases, brute force, serialization - CLI create support with --num-attributes, --dependencies, --relation-attrs, --known-keys - Module registration and re-exports - Canonical example-db entry with regenerated fixtures Co-Authored-By: Claude Opus 4.6 <[email protected]>

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

Implement the AdditionalKey satisfaction problem from relational database theory (Garey & Johnson A4 SR27). Includes model, CLI registration, unit tests, and example-db entry.

Add problem-def entry, display name, and bibliography reference (Beeri & Bernstein, 1979) for the Additional Key problem from relational database theory. Co-Authored-By: Claude Opus 4.6 <[email protected]>

GiggleLiu · 2026-03-16T18:04:50Z

Implementation Summary

Changes

src/models/misc/additional_key.rs — New model: AdditionalKey satisfaction problem (struct, constructor, closure computation, Problem/SatisfactionProblem trait impls, declare_variants!, canonical example-db entry)
src/unit_tests/models/misc/additional_key.rs — 13 unit tests (creation, evaluation, brute force, serialization, paper example)
src/models/misc/mod.rs — Module registration + example-db chain
src/models/mod.rs — Re-export
src/lib.rs — Prelude re-export
problemreductions-cli/src/cli.rs — CLI flags (--num-attributes, --dependencies, --relation-attrs, --known-keys)
problemreductions-cli/src/commands/create.rs — pred create AdditionalKey handler
src/example_db/fixtures/examples.json — Regenerated with new model
docs/paper/reductions.typ — problem-def("AdditionalKey") with display name, formal definition, background, and worked example
docs/paper/references.bib — Added beeri1979 citation

Deviations from Plan

src/unit_tests/trait_consistency.rs was removed in a prior refactor — skipped that step
Added AdditionalKey to prelude in src/lib.rs (discovered during spec review)

Open Questions

None

Verification

make test: 2173 tests passed
make clippy: clean
make paper: compiles cleanly

Copilot

Pull request overview

Adds a new NP-complete satisfaction model, AdditionalKey, representing the “additional candidate key” problem from relational database theory, and wires it into the library exports, CLI instance creation, examples, and paper.

Changes:

Introduce AdditionalKey model (schema registration, evaluation via FD closure + minimality + exclusion from known keys, example-db spec).
Add unit tests covering evaluation behavior, brute force solving, and serde round-trip.
Extend CLI pred create with new flags/parsing for AdditionalKey, and add an example-db fixture plus paper reference/definition.

Reviewed changes

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

Show a summary per file

File	Description
`src/models/misc/additional_key.rs`	New `AdditionalKey` model implementation, schema registration, variants declaration, and example-db spec.
`src/unit_tests/models/misc/additional_key.rs`	Unit tests for correctness, solver integration, and serialization.
`src/models/misc/mod.rs`	Registers the new misc module, re-exports `AdditionalKey`, and includes its example specs.
`src/models/mod.rs`	Re-exports `AdditionalKey` from `models::misc`.
`src/lib.rs`	Adds `AdditionalKey` to the crate prelude exports.
`problemreductions-cli/src/cli.rs`	Adds `AdditionalKey` CLI flags to `CreateArgs` and the “Flags by problem type” help section.
`problemreductions-cli/src/commands/create.rs`	Adds `AdditionalKey` instance parsing/creation and an example invocation string.
`src/example_db/fixtures/examples.json`	Adds an `AdditionalKey` model fixture with sample/optimal satisfying configs.
`docs/paper/references.bib`	Adds Beeri & Bernstein (1979) reference.
`docs/paper/reductions.typ`	Adds paper definition block and display name mapping for `AdditionalKey`.

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

src/models/misc/additional_key.rs

+            }
+        }
+        // Sort known_keys entries internally for consistent comparison
+        let known_keys: Vec<Vec<usize>> = known_keys
+            .into_iter()
+            .map(|mut k| {
+                k.sort_unstable();


src/models/misc/additional_key.rs

+//! dependencies F) that is not in K. A candidate key is a minimal set of
+//! attributes whose closure under F covers all of R.
+//!
+//! The problem is NP-complete (Garey & Johnson, SR7).


src/models/misc/additional_key.rs

+    /// Panics if any attribute index is >= `num_attributes`, or if
+    /// `relation_attrs` contains duplicates.


GiggleLiu · 2026-03-18T18:01:57Z

Agentic Review Report

Structural Check

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

16/16 structural checks passed.

Deterministic checks:

Whitelist: FAIL (false positive — files outside whitelist are expected: references.bib, CLI files, examples.json, src/lib.rs)
Completeness: PASS

Build status: make test PASS, make clippy PASS

Semantic review:

evaluate() correctness: ✅ — Correctly computes attribute closure via fixed-point iteration, checks closure covers R, verifies minimality (removing any single attribute breaks coverage), and confirms not in known_keys.
compute_closure() correctness: ✅ — Fixed-point loop iterates until no change; handles FDs referencing attributes outside R.
dims() correctness: ✅ — vec![2; relation_attrs.len()], one binary variable per relation attribute.
Minimality check: ✅ — Correctly removes each selected attribute and recomputes closure.
Known keys comparison: ✅ — Constructor sorts keys; evaluate sorts selected set before comparison.
Complexity string: ✅ — "2^num_relation_attrs * num_dependencies * num_attributes" matches brute-force bound.
Edge cases: ✅ — Empty selection, wrong config length, invalid variable values all return false.
Paper entry: ✅ — Definition matches implementation, example is correct, Beeri & Bernstein 1979 reference verified.

Issue compliance: 8/8 checks passed (name, definition, problem type, type params, config space, feasibility, objective, complexity all match issue #445).

Minor note (non-blocking): Constructor validates known_keys attributes are < num_attributes but does not validate they are subsets of relation_attrs. Permissive but not incorrect.

Quality Check

Design principles:

DRY: ✅ — No duplicated logic
KISS: ✅ — Straightforward implementation, clear sequential steps in evaluate()
HC/LC: ✅ — Clean separation between model, CLI parsing, and tests

Issues:

#	Severity	Issue	Location
1	Important	Missing panic-path tests: Constructor `new()` has 5 distinct `assert!` panic conditions (relation_attrs out-of-bounds, duplicates, dependency lhs/rhs out-of-bounds, known_keys out-of-bounds), none tested with `#[should_panic]`. Other models in the codebase test their panic paths.	`src/unit_tests/models/misc/additional_key.rs`
2	Important	No assertion on solution count in brute-force test: `test_additional_key_brute_force_all` asserts solutions are non-empty and each evaluates to `true`, but does not assert a specific count. For a deterministic instance, pinning the count catches permissive/restrictive bugs.	`src/unit_tests/models/misc/additional_key.rs:106-114`
3	Minor	Help text bracket convention: `--known-keys` shown without brackets in help text (`cli.rs:246`) but is actually optional. Should be `[--known-keys]` to match convention (e.g., `[--weights]`).	`problemreductions-cli/src/cli.rs:246`
4	Minor	Redundant test: `test_additional_key_paper_example` duplicates assertions already covered by `test_additional_key_evaluate_satisfying` and `test_additional_key_brute_force_all`.	`src/unit_tests/models/misc/additional_key.rs:133-144`

Agentic Feature Tests

Verdict: PASS — 0 critical issues

#	Command	Result	Notes
1	`pred list`	✅	AdditionalKey appears with correct complexity
2	`pred show AdditionalKey`	✅	4 fields, 0 reductions, correct complexity
3	`pred show AdditionalKey --json`	✅	JSON schema correct
4	`pred create --example AdditionalKey`	✅	Valid JSON: 6 attrs, 5 FDs, 3 known keys
5	`pred solve --solver brute-force` (canonical)	✅	Finds `[1,0,0,1,0,1]` (attrs {0,3,5}), manually verified
6	`pred solve` (default ILP)	✅	Correctly errors: no reduction path
7	`pred create AdditionalKey` (no flags)	✅	Shows usage help
8	`pred create AdditionalKey` (custom flags)	✅	Custom instance works
9	Pipe: `create	solve --solver brute-force -`	✅
10	File roundtrip: `create -o file && solve file`	✅	Serialization roundtrip works
11	Unsatisfiable instance (all keys known)	✅	Correctly reports no solution
12	Instance with additional key	✅	Finds correct solution
13	Proper subset relation_attrs	✅	Handles R ⊂ A correctly
14	Validation: out-of-range attribute	✅	Panics correctly
15	Validation: duplicate relation_attrs	✅	Panics correctly
16	`pred path AdditionalKey SAT`	✅	No reduction path (expected)
17	All 13 unit tests	✅	`cargo test additional_key` passes

Mathematical verification of solver output:

Instance: 6 attrs, R={0..5}, FDs: {0,1}→{2,3}, {2,3}→{4,5}, {4,5}→{0,1}, {0,2}→{3}, {3,5}→{1}; Known keys: {0,1}, {2,3}, {4,5}
Solution: {0,3,5} → closure chain: {0,3,5} → +{1} → +{2,3} → +{4,5} = {0,1,2,3,4,5} ✅
Minimality: removing any single attribute breaks coverage ✅
Novelty: {0,3,5} not in known_keys ✅

Build note: One pre-existing compiler warning (unreachable pattern at create.rs:241) — not introduced by this PR.

Generated by review-pipeline

# Conflicts: # docs/paper/reductions.typ # problemreductions-cli/src/cli.rs # problemreductions-cli/src/commands/create.rs # src/example_db/fixtures/examples.json # src/lib.rs # src/models/misc/mod.rs # src/models/mod.rs

The merge brought in API changes to ModelExampleSpec (removed `build` closure, added direct `instance`/`optimal_config`/`optimal_value` fields). Update AdditionalKey's canonical_model_example_specs to match. Co-Authored-By: Claude Opus 4.6 (1M context) <[email protected]>

- Add 5 #[should_panic] tests for constructor validation paths - Pin brute-force solution count to 2 (additional keys: {0,2} and {0,3,5}) - Fix --known-keys help text to use [brackets] for optional flag - Remove redundant test_additional_key_paper_example Co-Authored-By: Claude Opus 4.6 (1M context) <[email protected]>

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

Add plan for #445: [Model] AdditionalKey

a36c1f0

GiggleLiu and others added 5 commits March 17, 2026 01:50

Apply rustfmt formatting fixes

7fd2866

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

Add AdditionalKey model (Batch 1)

61eec60

Implement the AdditionalKey satisfaction problem from relational database theory (Garey & Johnson A4 SR27). Includes model, CLI registration, unit tests, and example-db entry.

Add AdditionalKey problem definition to paper

cbb53c1

Add problem-def entry, display name, and bibliography reference (Beeri & Bernstein, 1979) for the Additional Key problem from relational database theory. Co-Authored-By: Claude Opus 4.6 <[email protected]>

chore: remove plan file after implementation

262f635

GiggleLiu requested a review from Copilot March 16, 2026 18:05

Copilot started reviewing on behalf of GiggleLiu March 16, 2026 18:05 View session

Copilot AI reviewed Mar 16, 2026

View reviewed changes

isPANN self-assigned this Mar 19, 2026

isPANN and others added 5 commits March 20, 2026 01:23

Fix merge artifacts: fmt, missing fields in test helper

76e1efd

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

Cover data getter methods in creation test

8ca70f0

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

isPANN approved these changes Mar 19, 2026

View reviewed changes

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

GiggleLiu deleted the issue-445-additional-key branch April 12, 2026 00:53

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Fix #445: [Model] AdditionalKey#681

Fix #445: [Model] AdditionalKey#681
isPANN merged 11 commits intomainfrom
issue-445-additional-key

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

		/// Panics if any attribute index is >= `num_attributes`, or if
		/// `relation_attrs` contains duplicates.

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

Verification

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