problemreductions/models/set/
prime_attribute_name.rs

1//! Prime Attribute Name problem implementation.
2//!
3//! Given a set of attributes A, a collection of functional dependencies F on A,
4//! and a query attribute x, determine if x belongs to any candidate key of <A, F>.
5
6use crate::registry::{FieldInfo, ProblemSchemaEntry};
7use crate::traits::Problem;
8use serde::{Deserialize, Serialize};
9
10inventory::submit! {
11    ProblemSchemaEntry {
12        name: "PrimeAttributeName",
13        display_name: "Prime Attribute Name",
14        aliases: &[],
15        dimensions: &[],
16        module_path: module_path!(),
17        description: "Determine if an attribute belongs to any candidate key under functional dependencies",
18        fields: &[
19            FieldInfo { name: "num_attributes", type_name: "usize", description: "Number of attributes" },
20            FieldInfo { name: "dependencies", type_name: "Vec<(Vec<usize>, Vec<usize>)>", description: "Functional dependencies (lhs, rhs) pairs" },
21            FieldInfo { name: "query_attribute", type_name: "usize", description: "The query attribute index" },
22        ],
23    }
24}
25
26/// Prime Attribute Name decision problem.
27///
28/// Given a set A = {0, 1, ..., n-1} of attribute names, a collection F of
29/// functional dependencies on A, and a specified attribute x in A, determine
30/// whether x is a *prime attribute* -- i.e., whether there exists a candidate
31/// key K for <A, F> such that x is in K.
32///
33/// A *candidate key* is a minimal set K of attributes whose closure under F
34/// equals A. An attribute is *prime* if it belongs to at least one candidate key.
35///
36/// This is a classical NP-complete problem from relational database theory
37/// (Garey & Johnson SR28, Lucchesi & Osborne 1978).
38///
39/// # Example
40///
41/// ```
42/// use problemreductions::models::set::PrimeAttributeName;
43/// use problemreductions::{Problem, Solver, BruteForce};
44///
45/// // 6 attributes, FDs: {0,1}->rest, {2,3}->rest, {0,3}->rest
46/// let problem = PrimeAttributeName::new(
47///     6,
48///     vec![
49///         (vec![0, 1], vec![2, 3, 4, 5]),
50///         (vec![2, 3], vec![0, 1, 4, 5]),
51///         (vec![0, 3], vec![1, 2, 4, 5]),
52///     ],
53///     3,
54/// );
55///
56/// // {2, 3} is a candidate key containing attribute 3
57/// assert!(problem.evaluate(&[0, 0, 1, 1, 0, 0]));
58///
59/// let solver = BruteForce::new();
60/// let solution = solver.find_witness(&problem);
61/// assert!(solution.is_some());
62/// ```
63#[derive(Debug, Clone, Serialize, Deserialize)]
64pub struct PrimeAttributeName {
65    /// Number of attributes (elements are 0..num_attributes).
66    num_attributes: usize,
67    /// Functional dependencies as (lhs, rhs) pairs.
68    dependencies: Vec<(Vec<usize>, Vec<usize>)>,
69    /// The query attribute index.
70    query_attribute: usize,
71}
72
73impl PrimeAttributeName {
74    /// Create a new Prime Attribute Name problem.
75    ///
76    /// # Panics
77    ///
78    /// Panics if `query_attribute >= num_attributes`, if any attribute index
79    /// in a dependency is out of range, or if any LHS is empty.
80    pub fn new(
81        num_attributes: usize,
82        dependencies: Vec<(Vec<usize>, Vec<usize>)>,
83        query_attribute: usize,
84    ) -> Self {
85        assert!(
86            query_attribute < num_attributes,
87            "Query attribute {} is outside attribute set of size {}",
88            query_attribute,
89            num_attributes
90        );
91        for (i, (lhs, rhs)) in dependencies.iter().enumerate() {
92            assert!(!lhs.is_empty(), "Dependency {} has empty LHS", i);
93            for &attr in lhs.iter().chain(rhs.iter()) {
94                assert!(
95                    attr < num_attributes,
96                    "Dependency {} references attribute {} which is outside attribute set of size {}",
97                    i,
98                    attr,
99                    num_attributes
100                );
101            }
102        }
103        Self {
104            num_attributes,
105            dependencies,
106            query_attribute,
107        }
108    }
109
110    /// Get the number of attributes.
111    pub fn num_attributes(&self) -> usize {
112        self.num_attributes
113    }
114
115    /// Get the number of functional dependencies.
116    pub fn num_dependencies(&self) -> usize {
117        self.dependencies.len()
118    }
119
120    /// Get the query attribute index.
121    pub fn query_attribute(&self) -> usize {
122        self.query_attribute
123    }
124
125    /// Get the functional dependencies.
126    pub fn dependencies(&self) -> &[(Vec<usize>, Vec<usize>)] {
127        &self.dependencies
128    }
129
130    /// Compute the attribute closure of a set under the functional dependencies.
131    ///
132    /// Starting from the given boolean mask of attributes, repeatedly applies
133    /// all functional dependencies until a fixpoint is reached.
134    pub fn compute_closure(&self, attrs: &[bool]) -> Vec<bool> {
135        let mut closure = attrs.to_vec();
136        loop {
137            let mut changed = false;
138            for (lhs, rhs) in &self.dependencies {
139                if lhs.iter().all(|&a| closure[a]) {
140                    for &a in rhs {
141                        if !closure[a] {
142                            closure[a] = true;
143                            changed = true;
144                        }
145                    }
146                }
147            }
148            if !changed {
149                break;
150            }
151        }
152        closure
153    }
154}
155
156impl Problem for PrimeAttributeName {
157    const NAME: &'static str = "PrimeAttributeName";
158    type Value = crate::types::Or;
159
160    fn dims(&self) -> Vec<usize> {
161        vec![2; self.num_attributes]
162    }
163
164    fn evaluate(&self, config: &[usize]) -> crate::types::Or {
165        crate::types::Or({
166            // Check config length and binary values
167            if config.len() != self.num_attributes || config.iter().any(|&v| v > 1) {
168                return crate::types::Or(false);
169            }
170
171            // K = {i : config[i] = 1}
172            let k: Vec<bool> = config.iter().map(|&v| v == 1).collect();
173
174            // query_attribute must be in K
175            if !k[self.query_attribute] {
176                return crate::types::Or(false);
177            }
178
179            // Compute closure(K) -- must equal all attributes (K is a superkey)
180            let closure = self.compute_closure(&k);
181            if closure.iter().any(|&v| !v) {
182                return crate::types::Or(false);
183            }
184
185            // Check minimality: removing any attribute from K must break the superkey property
186            for i in 0..self.num_attributes {
187                if k[i] {
188                    let mut reduced = k.clone();
189                    reduced[i] = false;
190                    let reduced_closure = self.compute_closure(&reduced);
191                    if reduced_closure.iter().all(|&v| v) {
192                        // K \ {i} is still a superkey, so K is not minimal
193                        return crate::types::Or(false);
194                    }
195                }
196            }
197
198            true
199        })
200    }
201
202    fn variant() -> Vec<(&'static str, &'static str)> {
203        crate::variant_params![]
204    }
205}
206
207crate::declare_variants! {
208    default PrimeAttributeName => "2^num_attributes * num_dependencies * num_attributes",
209}
210
211#[cfg(feature = "example-db")]
212pub(crate) fn canonical_model_example_specs() -> Vec<crate::example_db::specs::ModelExampleSpec> {
213    vec![crate::example_db::specs::ModelExampleSpec {
214        id: "prime_attribute_name",
215        // Issue Example 1: 6 attributes, 3 FDs, query=3 -> YES
216        instance: Box::new(PrimeAttributeName::new(
217            6,
218            vec![
219                (vec![0, 1], vec![2, 3, 4, 5]),
220                (vec![2, 3], vec![0, 1, 4, 5]),
221                (vec![0, 3], vec![1, 2, 4, 5]),
222            ],
223            3,
224        )),
225        // {2, 3} is a candidate key containing attribute 3
226        optimal_config: vec![0, 0, 1, 1, 0, 0],
227        optimal_value: serde_json::json!(true),
228    }]
229}
230
231#[cfg(test)]
232#[path = "../../unit_tests/models/set/prime_attribute_name.rs"]
233mod tests;
problemreductions/models/set/prime_attribute_name.rs

problemreductions/models/set/
prime_attribute_name.rs
