problemreductions/models/set/
minimum_cardinality_key.rs

1//! Minimum Cardinality Key problem implementation.
2//!
3//! Given a set of attribute names and functional dependencies,
4//! find a candidate key of minimum cardinality.
5
6use crate::registry::{FieldInfo, ProblemSchemaEntry};
7use crate::traits::Problem;
8use crate::types::Min;
9use serde::{Deserialize, Serialize};
10
11inventory::submit! {
12    ProblemSchemaEntry {
13        name: "MinimumCardinalityKey",
14        display_name: "Minimum Cardinality Key",
15        aliases: &[],
16        dimensions: &[],
17        category: crate::registry::ProblemCategory::Set,
18        module_path: module_path!(),
19        description: "Find a candidate key of minimum cardinality in a relational system",
20        fields: &[
21            FieldInfo { name: "num_attributes", type_name: "usize", description: "Number of attributes in the relation" },
22            FieldInfo { name: "dependencies", type_name: "Vec<(Vec<usize>, Vec<usize>)>", description: "Functional dependencies as (lhs, rhs) pairs" },
23        ],
24    }
25}
26
27/// The Minimum Cardinality Key optimization problem.
28///
29/// Given a set of attributes `A = {0, ..., n-1}` and a set of functional
30/// dependencies `F` (each a pair `(X, Y)` where `X, Y` are subsets of `A`),
31/// find a subset `K ⊆ A` of minimum cardinality such that the closure of `K`
32/// under `F` equals `A` (i.e., `K` is a key).
33#[derive(Debug, Clone, Serialize, Deserialize)]
34#[serde(try_from = "MinimumCardinalityKeyData")]
35pub struct MinimumCardinalityKey {
36    /// Number of attributes (elements are `0..num_attributes`).
37    num_attributes: usize,
38    /// Functional dependencies as `(lhs, rhs)` pairs.
39    dependencies: Vec<(Vec<usize>, Vec<usize>)>,
40}
41
42#[derive(Deserialize)]
43struct MinimumCardinalityKeyData {
44    num_attributes: usize,
45    dependencies: Vec<(Vec<usize>, Vec<usize>)>,
46}
47
48impl TryFrom<MinimumCardinalityKeyData> for MinimumCardinalityKey {
49    type Error = crate::registry::ConstructionError;
50
51    fn try_from(data: MinimumCardinalityKeyData) -> Result<Self, Self::Error> {
52        Self::try_new(data.num_attributes, data.dependencies)
53    }
54}
55
56impl MinimumCardinalityKey {
57    /// Create a new Minimum Cardinality Key instance.
58    ///
59    /// # Panics
60    ///
61    /// Panics if any attribute index in a dependency lies outside the attribute set.
62    pub fn new(num_attributes: usize, dependencies: Vec<(Vec<usize>, Vec<usize>)>) -> Self {
63        Self::try_new(num_attributes, dependencies).unwrap_or_else(|error| panic!("{error}"))
64    }
65
66    fn try_new(
67        num_attributes: usize,
68        mut dependencies: Vec<(Vec<usize>, Vec<usize>)>,
69    ) -> Result<Self, crate::registry::ConstructionError> {
70        for (index, (lhs, rhs)) in dependencies.iter_mut().enumerate() {
71            lhs.sort_unstable();
72            lhs.dedup();
73            rhs.sort_unstable();
74            rhs.dedup();
75            if let Some(attribute) = lhs
76                .iter()
77                .chain(rhs.iter())
78                .find(|&&attribute| attribute >= num_attributes)
79            {
80                return Err(format!("dependency {index} contains attribute {attribute} outside attribute set of size {num_attributes}").into());
81            }
82        }
83        Ok(Self {
84            num_attributes,
85            dependencies,
86        })
87    }
88
89    /// Return the number of attributes.
90    pub fn num_attributes(&self) -> usize {
91        self.num_attributes
92    }
93
94    /// Return the number of functional dependencies.
95    pub fn num_dependencies(&self) -> usize {
96        self.dependencies.len()
97    }
98
99    /// Return the functional dependencies.
100    pub fn dependencies(&self) -> &[(Vec<usize>, Vec<usize>)] {
101        &self.dependencies
102    }
103
104    /// Compute the attribute closure of the selected attributes under the
105    /// functional dependencies. Starts with the selected set and repeatedly
106    /// applies each FD: if all lhs attributes are in the closure, add all rhs
107    /// attributes. Repeats until no change.
108    fn compute_closure(&self, selected: &[bool]) -> Vec<bool> {
109        let mut closure = selected.to_vec();
110        loop {
111            let mut changed = false;
112            for (lhs, rhs) in &self.dependencies {
113                if lhs.iter().all(|&a| closure[a]) {
114                    for &a in rhs {
115                        if !closure[a] {
116                            closure[a] = true;
117                            changed = true;
118                        }
119                    }
120                }
121            }
122            if !changed {
123                break;
124            }
125        }
126        closure
127    }
128
129    /// Check whether the selected attributes form a key (their closure equals
130    /// the full attribute set).
131    fn is_key(&self, selected: &[bool]) -> bool {
132        let closure = self.compute_closure(selected);
133        closure.iter().all(|&v| v)
134    }
135}
136
137impl Problem for MinimumCardinalityKey {
138    const NAME: &'static str = "MinimumCardinalityKey";
139    type Solution = Vec<bool>;
140    type Value = Min<i64>;
141
142    crate::problem_parameters![
143        ("num_attributes", num_attributes),
144        ("num_dependencies", num_dependencies),
145    ];
146
147    fn evaluate(
148        &self,
149        config: &Self::Solution,
150    ) -> Result<Min<i64>, crate::traits::EvaluationError> {
151        Ok({
152            if config.len() != self.num_attributes {
153                return Err(crate::traits::EvaluationError::InvalidConfiguration(
154                    "attribute-selection length does not match the relation".into(),
155                ));
156            }
157
158            if self.is_key(config) {
159                let count = config.iter().filter(|&&v| v).count();
160                Min(Some(i64::try_from(count).map_err(|_| {
161                    crate::traits::EvaluationError::IntegerOverflow(
162                        "converting selected-attribute count to i64".into(),
163                    )
164                })?))
165            } else {
166                Min(None)
167            }
168        })
169    }
170
171    fn variant() -> Vec<(&'static str, &'static str)> {
172        crate::variant_params![]
173    }
174}
175
176impl crate::solvers::BruteForceProblem for MinimumCardinalityKey {
177    fn dimensions(&self) -> Vec<usize> {
178        vec![2; self.num_attributes]
179    }
180}
181
182crate::declare_variants! {
183    default MinimumCardinalityKey => "2^num_attributes",
184}
185
186crate::register_brute_force! {
187    MinimumCardinalityKey decode |_, indices: Vec<usize>| crate::config::config_to_bits(&indices),
188}
189
190#[cfg(feature = "example-db")]
191pub(crate) fn canonical_model_example_specs() -> Vec<crate::example_db::specs::ModelExampleSpec> {
192    vec![crate::example_db::specs::ModelExampleSpec {
193        id: "minimum_cardinality_key",
194        instance: Box::new(MinimumCardinalityKey::new(
195            6,
196            vec![
197                (vec![0, 1], vec![2]),
198                (vec![0, 2], vec![3]),
199                (vec![1, 3], vec![4]),
200                (vec![2, 4], vec![5]),
201            ],
202        )),
203        optimal_config: serde_json::json!(vec![true, true, false, false, false, false]),
204        optimal_value: serde_json::json!(2),
205    }]
206}
207
208#[cfg(test)]
209#[path = "../../unit_tests/models/set/minimum_cardinality_key.rs"]
210mod tests;
problemreductions/models/set/minimum_cardinality_key.rs

problemreductions/models/set/
minimum_cardinality_key.rs
