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::{CreateSpec, 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        category: crate::registry::ProblemCategory::Misc,
20        module_path: module_path!(),
21        description: "Test whether a subset of attributes violates Boyce-Codd normal form",
22        fields: BoyceCoddNormalFormViolationCreateSpec::FIELDS,
23    }
24}
25
26/// The Boyce-Codd Normal Form Violation decision problem.
27///
28/// Given a set of attributes `A = {0, ..., num_attributes - 1}`, a collection of
29/// functional dependencies `F` over `A`, and a target subset `A' ⊆ A`, determine
30/// whether there exists a subset `X ⊆ A'` such that the closure `X⁺` under `F`
31/// contains some element of `A' \ X` but not all — witnessing a BCNF violation.
32///
33/// # Representation
34///
35/// A configuration is a binary vector of length `|A'|`, where bit `i = 1` means
36/// attribute `target_subset[i]` is included in the candidate set `X`.
37///
38/// # Example
39///
40/// ```
41/// use problemreductions::models::misc::BoyceCoddNormalFormViolation;
42/// use problemreductions::{Problem, BruteForce};
43///
44/// // 6 attributes, FDs: {0,1}→{2}, {2}→{3}, {3,4}→{5}
45/// let problem = BoyceCoddNormalFormViolation::new(
46///     6,
47///     vec![
48///         (vec![0, 1], vec![2]),
49///         (vec![2], vec![3]),
50///         (vec![3, 4], vec![5]),
51///     ],
52///     vec![0, 1, 2, 3, 4, 5],
53/// );
54/// let solver = BruteForce::new();
55/// // X = {2}: closure = {2, 3}, y=3 ∈ closure, z=0 ∉ closure → BCNF violation
56/// assert!(problem
57///     .evaluate(&vec![false, false, true, false, false, false])
58///     .unwrap());
59/// ```
60#[derive(Debug, Clone, Serialize, Deserialize)]
61pub struct BoyceCoddNormalFormViolation {
62    /// Total number of attributes (elements are `0..num_attributes`).
63    num_attributes: usize,
64    /// Functional dependencies as (lhs_attributes, rhs_attributes) pairs.
65    functional_deps: Vec<(Vec<usize>, Vec<usize>)>,
66    /// Target subset `A'` of attributes to test for BCNF violation.
67    target_subset: Vec<usize>,
68}
69
70#[derive(Debug, Deserialize, crate::CreateSpec)]
71struct BoyceCoddNormalFormViolationCreateSpec {
72    /// Total number of attributes in A.
73    n: usize,
74    /// Functional dependencies (lhs attributes, rhs attributes).
75    #[create(codec = "functional-dependency-list")]
76    subsets: Vec<(Vec<usize>, Vec<usize>)>,
77    /// Subset A' of attributes to test for BCNF violation.
78    target: Vec<usize>,
79}
80
81impl TryFrom<BoyceCoddNormalFormViolationCreateSpec> for BoyceCoddNormalFormViolation {
82    type Error = crate::registry::ConstructionError;
83
84    fn try_from(spec: BoyceCoddNormalFormViolationCreateSpec) -> Result<Self, Self::Error> {
85        if spec.target.is_empty() {
86            return Err("target must be non-empty".to_string().into());
87        }
88        for (dependency_index, (lhs, rhs)) in spec.subsets.iter().enumerate() {
89            if lhs.is_empty() {
90                return Err(format!("subsets[{dependency_index}] has an empty left side").into());
91            }
92            if let Some(&attribute) = lhs
93                .iter()
94                .chain(rhs)
95                .find(|&&attribute| attribute >= spec.n)
96            {
97                return Err(format!(
98                    "subsets[{dependency_index}] contains attribute {attribute} outside universe of size {}",
99                    spec.n
100                ).into());
101            }
102        }
103        if let Some(&attribute) = spec.target.iter().find(|&&attribute| attribute >= spec.n) {
104            return Err(format!(
105                "target contains attribute {attribute} outside universe of size {}",
106                spec.n
107            )
108            .into());
109        }
110        Ok(Self::new(spec.n, spec.subsets, spec.target))
111    }
112}
113
114impl BoyceCoddNormalFormViolation {
115    /// Create a new Boyce-Codd Normal Form Violation instance.
116    ///
117    /// # Panics
118    ///
119    /// Panics if any attribute index in `functional_deps` or `target_subset` is
120    /// out of range (≥ `num_attributes`), if `target_subset` is empty, or if any
121    /// functional dependency has an empty LHS.
122    ///
123    /// The constructor also normalizes the instance by sorting and deduplicating
124    /// every functional dependency LHS/RHS and the `target_subset`. As a result,
125    /// the configuration bit positions correspond to the normalized
126    /// `target_subset()` order rather than the caller's original input order.
127    pub fn new(
128        num_attributes: usize,
129        functional_deps: Vec<(Vec<usize>, Vec<usize>)>,
130        target_subset: Vec<usize>,
131    ) -> Self {
132        assert!(!target_subset.is_empty(), "target_subset must be non-empty");
133
134        let mut functional_deps = functional_deps;
135        for (fd_index, (lhs, rhs)) in functional_deps.iter_mut().enumerate() {
136            assert!(
137                !lhs.is_empty(),
138                "Functional dependency {} has an empty LHS",
139                fd_index
140            );
141            lhs.sort_unstable();
142            lhs.dedup();
143            rhs.sort_unstable();
144            rhs.dedup();
145            for &attr in lhs.iter().chain(rhs.iter()) {
146                assert!(
147                    attr < num_attributes,
148                    "Functional dependency {} contains attribute {} which is out of range (num_attributes = {})",
149                    fd_index,
150                    attr,
151                    num_attributes
152                );
153            }
154        }
155
156        let mut target_subset = target_subset;
157        target_subset.sort_unstable();
158        target_subset.dedup();
159        for &attr in &target_subset {
160            assert!(
161                attr < num_attributes,
162                "target_subset contains attribute {} which is out of range (num_attributes = {})",
163                attr,
164                num_attributes
165            );
166        }
167
168        Self {
169            num_attributes,
170            functional_deps,
171            target_subset,
172        }
173    }
174
175    /// Return the total number of attributes.
176    pub fn num_attributes(&self) -> usize {
177        self.num_attributes
178    }
179
180    /// Return the number of functional dependencies.
181    pub fn num_functional_deps(&self) -> usize {
182        self.functional_deps.len()
183    }
184
185    /// Return the number of attributes in the target subset.
186    pub fn num_target_attributes(&self) -> usize {
187        self.target_subset.len()
188    }
189
190    /// Return the functional dependencies.
191    pub fn functional_deps(&self) -> &[(Vec<usize>, Vec<usize>)] {
192        &self.functional_deps
193    }
194
195    /// Return the target subset `A'`.
196    pub fn target_subset(&self) -> &[usize] {
197        &self.target_subset
198    }
199
200    /// Compute the closure of a set of attributes under a collection of functional dependencies.
201    fn compute_closure(x: &HashSet<usize>, fds: &[(Vec<usize>, Vec<usize>)]) -> HashSet<usize> {
202        let mut closure = x.clone();
203        let mut changed = true;
204        while changed {
205            changed = false;
206            for (lhs, rhs) in fds {
207                if lhs.iter().all(|a| closure.contains(a)) {
208                    for &a in rhs {
209                        if closure.insert(a) {
210                            changed = true;
211                        }
212                    }
213                }
214            }
215        }
216        closure
217    }
218}
219
220impl Problem for BoyceCoddNormalFormViolation {
221    const NAME: &'static str = "BoyceCoddNormalFormViolation";
222    type Solution = Vec<bool>;
223    type Value = crate::types::Or;
224
225    crate::problem_parameters![
226        ("num_attributes", num_attributes),
227        ("num_functional_deps", num_functional_deps),
228        ("num_target_attributes", num_target_attributes),
229    ];
230
231    fn evaluate(
232        &self,
233        config: &Self::Solution,
234    ) -> Result<crate::types::Or, crate::traits::EvaluationError> {
235        Ok({
236            crate::types::Or({
237                if config.len() != self.target_subset.len() {
238                    return Err(crate::traits::EvaluationError::InvalidConfiguration(
239                        "attribute-selection length does not match the target subset".into(),
240                    ));
241                }
242                let x: HashSet<usize> = config
243                    .iter()
244                    .enumerate()
245                    .filter(|(_, &v)| v)
246                    .map(|(i, _)| self.target_subset[i])
247                    .collect();
248                let closure = Self::compute_closure(&x, &self.functional_deps);
249                // Check: ∃ y, z ∈ A' \ X s.t. y ∈ closure ∧ z ∉ closure
250                let mut has_in_closure = false;
251                let mut has_not_in_closure = false;
252                for &a in &self.target_subset {
253                    if !x.contains(&a) {
254                        if closure.contains(&a) {
255                            has_in_closure = true;
256                        } else {
257                            has_not_in_closure = true;
258                        }
259                    }
260                }
261                has_in_closure && has_not_in_closure
262            })
263        })
264    }
265
266    fn variant() -> Vec<(&'static str, &'static str)> {
267        crate::variant_params![]
268    }
269}
270
271impl crate::solvers::BruteForceProblem for BoyceCoddNormalFormViolation {
272    fn dimensions(&self) -> Vec<usize> {
273        vec![2; self.target_subset.len()]
274    }
275}
276
277crate::declare_variants! {
278    default BoyceCoddNormalFormViolation => "2^num_target_attributes * num_target_attributes^2 * num_functional_deps" create BoyceCoddNormalFormViolationCreateSpec,
279}
280
281crate::register_brute_force! {
282    BoyceCoddNormalFormViolation decode |_, indices: Vec<usize>| crate::config::config_to_bits(&indices),
283}
284
285#[cfg(feature = "example-db")]
286pub(crate) fn canonical_model_example_specs() -> Vec<crate::example_db::specs::ModelExampleSpec> {
287    vec![crate::example_db::specs::ModelExampleSpec {
288        id: "boyce_codd_normal_form_violation",
289        instance: Box::new(BoyceCoddNormalFormViolation::new(
290            6,
291            vec![
292                (vec![0, 1], vec![2]),
293                (vec![2], vec![3]),
294                (vec![3, 4], vec![5]),
295            ],
296            vec![0, 1, 2, 3, 4, 5],
297        )),
298        // X={2}: closure={2,3}, y=3 in closure, z=0 not in closure -> violation
299        optimal_config: serde_json::json!(vec![false, false, true, false, false, false]),
300        optimal_value: serde_json::json!(true),
301    }]
302}
303
304#[cfg(test)]
305#[path = "../../unit_tests/models/misc/boyce_codd_normal_form_violation.rs"]
306mod tests;
problemreductions/models/misc/boyce_codd_normal_form_violation.rs

problemreductions/models/misc/
boyce_codd_normal_form_violation.rs
