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)]
61#[serde(try_from = "BoyceCoddNormalFormViolationData")]
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
71#[derive(Deserialize)]
72struct BoyceCoddNormalFormViolationData {
73    num_attributes: usize,
74    functional_deps: Vec<(Vec<usize>, Vec<usize>)>,
75    target_subset: Vec<usize>,
76}
77
78impl TryFrom<BoyceCoddNormalFormViolationData> for BoyceCoddNormalFormViolation {
79    type Error = crate::registry::ConstructionError;
80    fn try_from(data: BoyceCoddNormalFormViolationData) -> Result<Self, Self::Error> {
81        Self::try_new(
82            data.num_attributes,
83            data.functional_deps,
84            data.target_subset,
85        )
86    }
87}
88
89#[derive(Debug, Deserialize, crate::CreateSpec)]
90struct BoyceCoddNormalFormViolationCreateSpec {
91    /// Total number of attributes in A.
92    n: usize,
93    /// Functional dependencies (lhs attributes, rhs attributes).
94    #[create(codec = "functional-dependency-list")]
95    subsets: Vec<(Vec<usize>, Vec<usize>)>,
96    /// Subset A' of attributes to test for BCNF violation.
97    target: Vec<usize>,
98}
99
100impl TryFrom<BoyceCoddNormalFormViolationCreateSpec> for BoyceCoddNormalFormViolation {
101    type Error = crate::registry::ConstructionError;
102
103    fn try_from(spec: BoyceCoddNormalFormViolationCreateSpec) -> Result<Self, Self::Error> {
104        Self::try_new(spec.n, spec.subsets, spec.target)
105    }
106}
107
108impl BoyceCoddNormalFormViolation {
109    /// Create a new Boyce-Codd Normal Form Violation instance.
110    ///
111    /// # Panics
112    ///
113    /// Panics if any attribute index in `functional_deps` or `target_subset` is
114    /// out of range (≥ `num_attributes`), if `target_subset` is empty, or if any
115    /// functional dependency has an empty LHS.
116    ///
117    /// The constructor also normalizes the instance by sorting and deduplicating
118    /// every functional dependency LHS/RHS and the `target_subset`. As a result,
119    /// the configuration bit positions correspond to the normalized
120    /// `target_subset()` order rather than the caller's original input order.
121    pub fn new(
122        num_attributes: usize,
123        functional_deps: Vec<(Vec<usize>, Vec<usize>)>,
124        target_subset: Vec<usize>,
125    ) -> Self {
126        Self::try_new(num_attributes, functional_deps, target_subset)
127            .unwrap_or_else(|error| panic!("{error}"))
128    }
129
130    fn try_new(
131        num_attributes: usize,
132        functional_deps: Vec<(Vec<usize>, Vec<usize>)>,
133        target_subset: Vec<usize>,
134    ) -> Result<Self, crate::registry::ConstructionError> {
135        if target_subset.is_empty() {
136            return Err("target_subset must be non-empty".into());
137        }
138
139        let mut functional_deps = functional_deps;
140        for (fd_index, (lhs, rhs)) in functional_deps.iter_mut().enumerate() {
141            if lhs.is_empty() {
142                return Err(format!("Functional dependency {} has an empty LHS", fd_index).into());
143            }
144            lhs.sort_unstable();
145            lhs.dedup();
146            rhs.sort_unstable();
147            rhs.dedup();
148            for &attr in lhs.iter().chain(rhs.iter()) {
149                if attr >= num_attributes {
150                    return Err(format!("Functional dependency {} contains attribute {} which is out of range (num_attributes = {})", fd_index, attr, num_attributes).into());
151                }
152            }
153        }
154
155        let mut target_subset = target_subset;
156        target_subset.sort_unstable();
157        target_subset.dedup();
158        for &attr in &target_subset {
159            if attr >= num_attributes {
160                return Err(format!("target_subset contains attribute {} which is out of range (num_attributes = {})", attr, num_attributes).into());
161            }
162        }
163
164        Ok(Self {
165            num_attributes,
166            functional_deps,
167            target_subset,
168        })
169    }
170
171    /// Return the total number of attributes.
172    pub fn num_attributes(&self) -> usize {
173        self.num_attributes
174    }
175
176    /// Return the number of functional dependencies.
177    pub fn num_functional_deps(&self) -> usize {
178        self.functional_deps.len()
179    }
180
181    /// Return the number of attributes in the target subset.
182    pub fn num_target_attributes(&self) -> usize {
183        self.target_subset.len()
184    }
185
186    /// Return the functional dependencies.
187    pub fn functional_deps(&self) -> &[(Vec<usize>, Vec<usize>)] {
188        &self.functional_deps
189    }
190
191    /// Return the target subset `A'`.
192    pub fn target_subset(&self) -> &[usize] {
193        &self.target_subset
194    }
195
196    /// Compute the closure of a set of attributes under a collection of functional dependencies.
197    fn compute_closure(x: &HashSet<usize>, fds: &[(Vec<usize>, Vec<usize>)]) -> HashSet<usize> {
198        let mut closure = x.clone();
199        let mut changed = true;
200        while changed {
201            changed = false;
202            for (lhs, rhs) in fds {
203                if lhs.iter().all(|a| closure.contains(a)) {
204                    for &a in rhs {
205                        if closure.insert(a) {
206                            changed = true;
207                        }
208                    }
209                }
210            }
211        }
212        closure
213    }
214}
215
216impl Problem for BoyceCoddNormalFormViolation {
217    const NAME: &'static str = "BoyceCoddNormalFormViolation";
218    type Solution = Vec<bool>;
219    type Value = crate::types::Or;
220
221    crate::problem_parameters![
222        ("num_attributes", num_attributes),
223        ("num_functional_deps", num_functional_deps),
224        ("num_target_attributes", num_target_attributes),
225    ];
226
227    fn evaluate(
228        &self,
229        config: &Self::Solution,
230    ) -> Result<crate::types::Or, crate::traits::EvaluationError> {
231        Ok({
232            crate::types::Or({
233                if config.len() != self.target_subset.len() {
234                    return Err(crate::traits::EvaluationError::InvalidConfiguration(
235                        "attribute-selection length does not match the target subset".into(),
236                    ));
237                }
238                let x: HashSet<usize> = config
239                    .iter()
240                    .enumerate()
241                    .filter(|(_, &v)| v)
242                    .map(|(i, _)| self.target_subset[i])
243                    .collect();
244                let closure = Self::compute_closure(&x, &self.functional_deps);
245                // Check: ∃ y, z ∈ A' \ X s.t. y ∈ closure ∧ z ∉ closure
246                let mut has_in_closure = false;
247                let mut has_not_in_closure = false;
248                for &a in &self.target_subset {
249                    if !x.contains(&a) {
250                        if closure.contains(&a) {
251                            has_in_closure = true;
252                        } else {
253                            has_not_in_closure = true;
254                        }
255                    }
256                }
257                has_in_closure && has_not_in_closure
258            })
259        })
260    }
261
262    fn variant() -> Vec<(&'static str, &'static str)> {
263        crate::variant_params![]
264    }
265}
266
267impl crate::solvers::BruteForceProblem for BoyceCoddNormalFormViolation {
268    fn dimensions(&self) -> Vec<usize> {
269        vec![2; self.target_subset.len()]
270    }
271}
272
273crate::declare_variants! {
274    default BoyceCoddNormalFormViolation => "2^num_target_attributes * num_target_attributes^2 * num_functional_deps" create BoyceCoddNormalFormViolationCreateSpec,
275}
276
277crate::register_brute_force! {
278    BoyceCoddNormalFormViolation decode |_, indices: Vec<usize>| crate::config::config_to_bits(&indices),
279}
280
281#[cfg(feature = "example-db")]
282pub(crate) fn canonical_model_example_specs() -> Vec<crate::example_db::specs::ModelExampleSpec> {
283    vec![crate::example_db::specs::ModelExampleSpec {
284        id: "boyce_codd_normal_form_violation",
285        instance: Box::new(BoyceCoddNormalFormViolation::new(
286            6,
287            vec![
288                (vec![0, 1], vec![2]),
289                (vec![2], vec![3]),
290                (vec![3, 4], vec![5]),
291            ],
292            vec![0, 1, 2, 3, 4, 5],
293        )),
294        // X={2}: closure={2,3}, y=3 in closure, z=0 not in closure -> violation
295        optimal_config: serde_json::json!(vec![false, false, true, false, false, false]),
296        optimal_value: serde_json::json!(true),
297    }]
298}
299
300#[cfg(test)]
301#[path = "../../unit_tests/models/misc/boyce_codd_normal_form_violation.rs"]
302mod tests;
problemreductions/models/misc/boyce_codd_normal_form_violation.rs

problemreductions/models/misc/
boyce_codd_normal_form_violation.rs
