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        module_path: module_path!(),
18        description: "Find a candidate key of minimum cardinality in a relational system",
19        fields: &[
20            FieldInfo { name: "num_attributes", type_name: "usize", description: "Number of attributes in the relation" },
21            FieldInfo { name: "dependencies", type_name: "Vec<(Vec<usize>, Vec<usize>)>", description: "Functional dependencies as (lhs, rhs) pairs" },
22        ],
23    }
24}
25
26/// The Minimum Cardinality Key optimization problem.
27///
28/// Given a set of attributes `A = {0, ..., n-1}` and a set of functional
29/// dependencies `F` (each a pair `(X, Y)` where `X, Y` are subsets of `A`),
30/// find a subset `K ⊆ A` of minimum cardinality such that the closure of `K`
31/// under `F` equals `A` (i.e., `K` is a key).
32#[derive(Debug, Clone, Serialize, Deserialize)]
33pub struct MinimumCardinalityKey {
34    /// Number of attributes (elements are `0..num_attributes`).
35    num_attributes: usize,
36    /// Functional dependencies as `(lhs, rhs)` pairs.
37    dependencies: Vec<(Vec<usize>, Vec<usize>)>,
38}
39
40impl MinimumCardinalityKey {
41    /// Create a new Minimum Cardinality Key instance.
42    ///
43    /// # Panics
44    ///
45    /// Panics if any attribute index in a dependency lies outside the attribute set.
46    pub fn new(num_attributes: usize, dependencies: Vec<(Vec<usize>, Vec<usize>)>) -> Self {
47        let mut dependencies = dependencies;
48        for (dep_index, (lhs, rhs)) in dependencies.iter_mut().enumerate() {
49            lhs.sort_unstable();
50            lhs.dedup();
51            rhs.sort_unstable();
52            rhs.dedup();
53            for &attr in lhs.iter().chain(rhs.iter()) {
54                assert!(
55                    attr < num_attributes,
56                    "Dependency {} contains attribute {} which is outside attribute set of size {}",
57                    dep_index,
58                    attr,
59                    num_attributes
60                );
61            }
62        }
63
64        Self {
65            num_attributes,
66            dependencies,
67        }
68    }
69
70    /// Return the number of attributes.
71    pub fn num_attributes(&self) -> usize {
72        self.num_attributes
73    }
74
75    /// Return the number of functional dependencies.
76    pub fn num_dependencies(&self) -> usize {
77        self.dependencies.len()
78    }
79
80    /// Return the functional dependencies.
81    pub fn dependencies(&self) -> &[(Vec<usize>, Vec<usize>)] {
82        &self.dependencies
83    }
84
85    /// Compute the attribute closure of the selected attributes under the
86    /// functional dependencies. Starts with the selected set and repeatedly
87    /// applies each FD: if all lhs attributes are in the closure, add all rhs
88    /// attributes. Repeats until no change.
89    fn compute_closure(&self, selected: &[bool]) -> Vec<bool> {
90        let mut closure = selected.to_vec();
91        loop {
92            let mut changed = false;
93            for (lhs, rhs) in &self.dependencies {
94                if lhs.iter().all(|&a| closure[a]) {
95                    for &a in rhs {
96                        if !closure[a] {
97                            closure[a] = true;
98                            changed = true;
99                        }
100                    }
101                }
102            }
103            if !changed {
104                break;
105            }
106        }
107        closure
108    }
109
110    /// Check whether the selected attributes form a key (their closure equals
111    /// the full attribute set).
112    fn is_key(&self, selected: &[bool]) -> bool {
113        let closure = self.compute_closure(selected);
114        closure.iter().all(|&v| v)
115    }
116}
117
118impl Problem for MinimumCardinalityKey {
119    const NAME: &'static str = "MinimumCardinalityKey";
120    type Value = Min<i64>;
121
122    fn dims(&self) -> Vec<usize> {
123        vec![2; self.num_attributes]
124    }
125
126    fn evaluate(&self, config: &[usize]) -> Min<i64> {
127        if config.len() != self.num_attributes || config.iter().any(|&v| v > 1) {
128            return Min(None);
129        }
130
131        let selected: Vec<bool> = config.iter().map(|&v| v == 1).collect();
132
133        if self.is_key(&selected) {
134            let count = selected.iter().filter(|&&v| v).count();
135            Min(Some(count as i64))
136        } else {
137            Min(None)
138        }
139    }
140
141    fn variant() -> Vec<(&'static str, &'static str)> {
142        crate::variant_params![]
143    }
144}
145
146crate::declare_variants! {
147    default MinimumCardinalityKey => "2^num_attributes",
148}
149
150#[cfg(feature = "example-db")]
151pub(crate) fn canonical_model_example_specs() -> Vec<crate::example_db::specs::ModelExampleSpec> {
152    vec![crate::example_db::specs::ModelExampleSpec {
153        id: "minimum_cardinality_key",
154        instance: Box::new(MinimumCardinalityKey::new(
155            6,
156            vec![
157                (vec![0, 1], vec![2]),
158                (vec![0, 2], vec![3]),
159                (vec![1, 3], vec![4]),
160                (vec![2, 4], vec![5]),
161            ],
162        )),
163        optimal_config: vec![1, 1, 0, 0, 0, 0],
164        optimal_value: serde_json::json!(2),
165    }]
166}
167
168#[cfg(test)]
169#[path = "../../unit_tests/models/set/minimum_cardinality_key.rs"]
170mod tests;
problemreductions/models/set/minimum_cardinality_key.rs

problemreductions/models/set/
minimum_cardinality_key.rs
