Struct BoyceCoddNormalFormViolation 

pub struct BoyceCoddNormalFormViolation { /* private fields */ }

The Boyce-Codd Normal Form Violation decision problem.

Given a set of attributes A = {0, ..., num_attributes - 1}, a collection of functional dependencies F over A, and a target subset A' ⊆ A, determine whether there exists a subset X ⊆ A' such that the closure X⁺ under F contains some element of A' \ X but not all — witnessing a BCNF violation.

Representation

A configuration is a binary vector of length |A'|, where bit i = 1 means attribute target_subset[i] is included in the candidate set X.

Example

use problemreductions::models::misc::BoyceCoddNormalFormViolation;
use problemreductions::{Problem, Solver, BruteForce};

// 6 attributes, FDs: {0,1}→{2}, {2}→{3}, {3,4}→{5}
let problem = BoyceCoddNormalFormViolation::new(
    6,
    vec![
        (vec![0, 1], vec![2]),
        (vec![2], vec![3]),
        (vec![3, 4], vec![5]),
    ],
    vec![0, 1, 2, 3, 4, 5],
);
let solver = BruteForce::new();
// X = {2}: closure = {2, 3}, y=3 ∈ closure, z=0 ∉ closure → BCNF violation
assert!(problem.evaluate(&[0, 0, 1, 0, 0, 0]));

Implementations

impl BoyceCoddNormalFormViolation

pub fn new( num_attributes: usize, functional_deps: Vec<(Vec<usize>, Vec<usize>)>, target_subset: Vec<usize>, ) -> Self

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.

The constructor also normalizes the instance by sorting and deduplicating every functional dependency LHS/RHS and the target_subset. As a result, the configuration bit positions correspond to the normalized target_subset() order rather than the caller’s original input order.

pub fn num_attributes(&self) -> usize

Return the total number of attributes.

pub fn num_functional_deps(&self) -> usize

Return the number of functional dependencies.

pub fn num_target_attributes(&self) -> usize

Return the number of attributes in the target subset.

pub fn functional_deps(&self) -> &[(Vec<usize>, Vec<usize>)]

Return the functional dependencies.

pub fn target_subset(&self) -> &[usize]

Return the target subset A'.

Trait Implementations

impl Clone for BoyceCoddNormalFormViolation

fn clone(&self) -> BoyceCoddNormalFormViolation

Returns a duplicate of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl Debug for BoyceCoddNormalFormViolation

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl<'de> Deserialize<'de> for BoyceCoddNormalFormViolation

fn deserialize<__D>(__deserializer: __D) -> Result<Self, __D::Error>

where __D: Deserializer<'de>,

Deserialize this value from the given Serde deserializer.

impl Problem for BoyceCoddNormalFormViolation

const NAME: &'static str = "BoyceCoddNormalFormViolation"

Base name of this problem type (e.g., “MaximumIndependentSet”).

type Value = Or

The evaluation value type.

fn dims(&self) -> Vec<usize>

Configuration space dimensions. Each entry is the cardinality of that variable.

fn evaluate(&self, config: &[usize]) -> Or

Evaluate the problem on a configuration.

fn variant() -> Vec<(&'static str, &'static str)>

Returns variant attributes derived from type parameters.

fn num_variables(&self) -> usize

Number of variables (derived from dims).

fn problem_type() -> ProblemType

Look up this problem’s catalog entry.

impl Serialize for BoyceCoddNormalFormViolation

fn serialize<__S>(&self, __serializer: __S) -> Result<__S::Ok, __S::Error>

where __S: Serializer,

Serialize this value into the given Serde serializer.

impl DeclaredVariant for BoyceCoddNormalFormViolation