problemreductions/models/misc/
boyce_codd_normal_form_violation.rs

1//! Boyce-Codd Normal Form Violation problem implementation.
2//!
3//! Given a set of attributes `A`, a collection of functional dependencies over `A`,
4//! and a target subset `A' ⊆ A`, determine whether there exists a non-trivial subset
5//! `X ⊆ A'` such that the closure of `X` under the functional dependencies contains
6//! some but not all attributes of `A' \ X` — i.e., a witness to a BCNF violation.
7
8use crate::registry::{FieldInfo, ProblemSchemaEntry};
9use crate::traits::Problem;
10use serde::{Deserialize, Serialize};
11use std::collections::HashSet;
12
13inventory::submit! {
14    ProblemSchemaEntry {
15        name: "BoyceCoddNormalFormViolation",
16        display_name: "Boyce-Codd Normal Form Violation",
17        aliases: &["BCNFViolation", "BCNF"],
18        dimensions: &[],
19        module_path: module_path!(),
20        description: "Test whether a subset of attributes violates Boyce-Codd normal form",
21        fields: &[
22            FieldInfo { name: "num_attributes", type_name: "usize", description: "Total number of attributes in A" },
23            FieldInfo { name: "functional_deps", type_name: "Vec<(Vec<usize>, Vec<usize>)>", description: "Functional dependencies (lhs_attributes, rhs_attributes)" },
24            FieldInfo { name: "target_subset", type_name: "Vec<usize>", description: "Subset A' of attributes to test for BCNF violation" },
25        ],
26    }
27}
28
29/// The Boyce-Codd Normal Form Violation decision problem.
30///
31/// Given a set of attributes `A = {0, ..., num_attributes - 1}`, a collection of
32/// functional dependencies `F` over `A`, and a target subset `A' ⊆ A`, determine
33/// whether there exists a subset `X ⊆ A'` such that the closure `X⁺` under `F`
34/// contains some element of `A' \ X` but not all — witnessing a BCNF violation.
35///
36/// # Representation
37///
38/// A configuration is a binary vector of length `|A'|`, where bit `i = 1` means
39/// attribute `target_subset[i]` is included in the candidate set `X`.
40///
41/// # Example
42///
43/// ```
44/// use problemreductions::models::misc::BoyceCoddNormalFormViolation;
45/// use problemreductions::{Problem, Solver, BruteForce};
46///
47/// // 6 attributes, FDs: {0,1}→{2}, {2}→{3}, {3,4}→{5}
48/// let problem = BoyceCoddNormalFormViolation::new(
49///     6,
50///     vec![
51///         (vec![0, 1], vec![2]),
52///         (vec![2], vec![3]),
53///         (vec![3, 4], vec![5]),
54///     ],
55///     vec![0, 1, 2, 3, 4, 5],
56/// );
57/// let solver = BruteForce::new();
58/// // X = {2}: closure = {2, 3}, y=3 ∈ closure, z=0 ∉ closure → BCNF violation
59/// assert!(problem.evaluate(&[0, 0, 1, 0, 0, 0]));
60/// ```
61#[derive(Debug, Clone, Serialize, Deserialize)]
62pub struct BoyceCoddNormalFormViolation {
63    /// Total number of attributes (elements are `0..num_attributes`).
64    num_attributes: usize,
65    /// Functional dependencies as (lhs_attributes, rhs_attributes) pairs.
66    functional_deps: Vec<(Vec<usize>, Vec<usize>)>,
67    /// Target subset `A'` of attributes to test for BCNF violation.
68    target_subset: Vec<usize>,
69}
70
71impl BoyceCoddNormalFormViolation {
72    /// Create a new Boyce-Codd Normal Form Violation instance.
73    ///
74    /// # Panics
75    ///
76    /// Panics if any attribute index in `functional_deps` or `target_subset` is
77    /// out of range (≥ `num_attributes`), if `target_subset` is empty, or if any
78    /// functional dependency has an empty LHS.
79    ///
80    /// The constructor also normalizes the instance by sorting and deduplicating
81    /// every functional dependency LHS/RHS and the `target_subset`. As a result,
82    /// the configuration bit positions correspond to the normalized
83    /// `target_subset()` order rather than the caller's original input order.
84    pub fn new(
85        num_attributes: usize,
86        functional_deps: Vec<(Vec<usize>, Vec<usize>)>,
87        target_subset: Vec<usize>,
88    ) -> Self {
89        assert!(!target_subset.is_empty(), "target_subset must be non-empty");
90
91        let mut functional_deps = functional_deps;
92        for (fd_index, (lhs, rhs)) in functional_deps.iter_mut().enumerate() {
93            assert!(
94                !lhs.is_empty(),
95                "Functional dependency {} has an empty LHS",
96                fd_index
97            );
98            lhs.sort_unstable();
99            lhs.dedup();
100            rhs.sort_unstable();
101            rhs.dedup();
102            for &attr in lhs.iter().chain(rhs.iter()) {
103                assert!(
104                    attr < num_attributes,
105                    "Functional dependency {} contains attribute {} which is out of range (num_attributes = {})",
106                    fd_index,
107                    attr,
108                    num_attributes
109                );
110            }
111        }
112
113        let mut target_subset = target_subset;
114        target_subset.sort_unstable();
115        target_subset.dedup();
116        for &attr in &target_subset {
117            assert!(
118                attr < num_attributes,
119                "target_subset contains attribute {} which is out of range (num_attributes = {})",
120                attr,
121                num_attributes
122            );
123        }
124
125        Self {
126            num_attributes,
127            functional_deps,
128            target_subset,
129        }
130    }
131
132    /// Return the total number of attributes.
133    pub fn num_attributes(&self) -> usize {
134        self.num_attributes
135    }
136
137    /// Return the number of functional dependencies.
138    pub fn num_functional_deps(&self) -> usize {
139        self.functional_deps.len()
140    }
141
142    /// Return the number of attributes in the target subset.
143    pub fn num_target_attributes(&self) -> usize {
144        self.target_subset.len()
145    }
146
147    /// Return the functional dependencies.
148    pub fn functional_deps(&self) -> &[(Vec<usize>, Vec<usize>)] {
149        &self.functional_deps
150    }
151
152    /// Return the target subset `A'`.
153    pub fn target_subset(&self) -> &[usize] {
154        &self.target_subset
155    }
156
157    /// Compute the closure of a set of attributes under a collection of functional dependencies.
158    fn compute_closure(x: &HashSet<usize>, fds: &[(Vec<usize>, Vec<usize>)]) -> HashSet<usize> {
159        let mut closure = x.clone();
160        let mut changed = true;
161        while changed {
162            changed = false;
163            for (lhs, rhs) in fds {
164                if lhs.iter().all(|a| closure.contains(a)) {
165                    for &a in rhs {
166                        if closure.insert(a) {
167                            changed = true;
168                        }
169                    }
170                }
171            }
172        }
173        closure
174    }
175}
176
177impl Problem for BoyceCoddNormalFormViolation {
178    const NAME: &'static str = "BoyceCoddNormalFormViolation";
179    type Value = crate::types::Or;
180
181    fn dims(&self) -> Vec<usize> {
182        vec![2; self.target_subset.len()]
183    }
184
185    fn evaluate(&self, config: &[usize]) -> crate::types::Or {
186        crate::types::Or({
187            if config.len() != self.target_subset.len() || config.iter().any(|&v| v > 1) {
188                return crate::types::Or(false);
189            }
190            let x: HashSet<usize> = config
191                .iter()
192                .enumerate()
193                .filter(|(_, &v)| v == 1)
194                .map(|(i, _)| self.target_subset[i])
195                .collect();
196            let closure = Self::compute_closure(&x, &self.functional_deps);
197            // Check: ∃ y, z ∈ A' \ X s.t. y ∈ closure ∧ z ∉ closure
198            let mut has_in_closure = false;
199            let mut has_not_in_closure = false;
200            for &a in &self.target_subset {
201                if !x.contains(&a) {
202                    if closure.contains(&a) {
203                        has_in_closure = true;
204                    } else {
205                        has_not_in_closure = true;
206                    }
207                }
208            }
209            has_in_closure && has_not_in_closure
210        })
211    }
212
213    fn variant() -> Vec<(&'static str, &'static str)> {
214        crate::variant_params![]
215    }
216}
217
218crate::declare_variants! {
219    default BoyceCoddNormalFormViolation => "2^num_target_attributes * num_target_attributes^2 * num_functional_deps",
220}
221
222#[cfg(feature = "example-db")]
223pub(crate) fn canonical_model_example_specs() -> Vec<crate::example_db::specs::ModelExampleSpec> {
224    vec![crate::example_db::specs::ModelExampleSpec {
225        id: "boyce_codd_normal_form_violation",
226        instance: Box::new(BoyceCoddNormalFormViolation::new(
227            6,
228            vec![
229                (vec![0, 1], vec![2]),
230                (vec![2], vec![3]),
231                (vec![3, 4], vec![5]),
232            ],
233            vec![0, 1, 2, 3, 4, 5],
234        )),
235        // X={2}: closure={2,3}, y=3 in closure, z=0 not in closure -> violation
236        optimal_config: vec![0, 0, 1, 0, 0, 0],
237        optimal_value: serde_json::json!(true),
238    }]
239}
240
241#[cfg(test)]
242#[path = "../../unit_tests/models/misc/boyce_codd_normal_form_violation.rs"]
243mod tests;
problemreductions/models/misc/boyce_codd_normal_form_violation.rs

problemreductions/models/misc/
boyce_codd_normal_form_violation.rs
