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::{CreateSpec, 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        category: crate::registry::ProblemCategory::Set,
17        module_path: module_path!(),
18        description: "Determine if an attribute belongs to any candidate key under functional dependencies",
19        fields: PrimeAttributeNameCreateSpec::FIELDS,
20    }
21}
22
23/// Prime Attribute Name decision problem.
24///
25/// Given a set A = {0, 1, ..., n-1} of attribute names, a collection F of
26/// functional dependencies on A, and a specified attribute x in A, determine
27/// whether x is a *prime attribute* -- i.e., whether there exists a candidate
28/// key K for <A, F> such that x is in K.
29///
30/// A *candidate key* is a minimal set K of attributes whose closure under F
31/// equals A. An attribute is *prime* if it belongs to at least one candidate key.
32///
33/// This is a classical NP-complete problem from relational database theory
34/// (Garey & Johnson SR28, Lucchesi & Osborne 1978).
35///
36/// # Example
37///
38/// ```
39/// use problemreductions::models::set::PrimeAttributeName;
40/// use problemreductions::{Problem, BruteForce};
41///
42/// // 6 attributes, FDs: {0,1}->rest, {2,3}->rest, {0,3}->rest
43/// let problem = PrimeAttributeName::new(
44///     6,
45///     vec![
46///         (vec![0, 1], vec![2, 3, 4, 5]),
47///         (vec![2, 3], vec![0, 1, 4, 5]),
48///         (vec![0, 3], vec![1, 2, 4, 5]),
49///     ],
50///     3,
51/// );
52///
53/// // {2, 3} is a candidate key containing attribute 3
54/// assert!(problem
55///     .evaluate(&vec![false, false, true, true, false, false])
56///     .unwrap());
57///
58/// let solver = BruteForce::new();
59/// let solution = solver.solve(&problem).unwrap();
60/// assert!(solution.is_some());
61/// ```
62#[derive(Debug, Clone, Serialize, Deserialize)]
63pub struct PrimeAttributeName {
64    /// Number of attributes (elements are 0..num_attributes).
65    num_attributes: usize,
66    /// Functional dependencies as (lhs, rhs) pairs.
67    dependencies: Vec<(Vec<usize>, Vec<usize>)>,
68    /// The query attribute index.
69    query_attribute: usize,
70}
71
72#[derive(Debug, Deserialize, crate::CreateSpec)]
73struct PrimeAttributeNameCreateSpec {
74    /// Number of attributes.
75    universe_size: usize,
76    /// Functional dependencies (lhs, rhs) pairs.
77    dependencies: Vec<(Vec<usize>, Vec<usize>)>,
78    /// The query attribute index.
79    query_attribute: usize,
80}
81
82impl TryFrom<PrimeAttributeNameCreateSpec> for PrimeAttributeName {
83    type Error = crate::registry::ConstructionError;
84
85    fn try_from(spec: PrimeAttributeNameCreateSpec) -> Result<Self, Self::Error> {
86        if spec.query_attribute >= spec.universe_size {
87            return Err(format!(
88                "query_attribute {} is outside universe of size {}",
89                spec.query_attribute, spec.universe_size
90            )
91            .into());
92        }
93        for (dependency_index, (lhs, rhs)) in spec.dependencies.iter().enumerate() {
94            if lhs.is_empty() {
95                return Err(
96                    format!("dependencies[{dependency_index}] has an empty left side").into(),
97                );
98            }
99            if let Some(&attribute) = lhs
100                .iter()
101                .chain(rhs)
102                .find(|&&attribute| attribute >= spec.universe_size)
103            {
104                return Err(format!(
105                    "dependencies[{dependency_index}] contains attribute {attribute} outside universe of size {}",
106                    spec.universe_size
107                ).into());
108            }
109        }
110        Ok(Self::new(
111            spec.universe_size,
112            spec.dependencies,
113            spec.query_attribute,
114        ))
115    }
116}
117
118impl PrimeAttributeName {
119    /// Create a new Prime Attribute Name problem.
120    ///
121    /// # Panics
122    ///
123    /// Panics if `query_attribute >= num_attributes`, if any attribute index
124    /// in a dependency is out of range, or if any LHS is empty.
125    pub fn new(
126        num_attributes: usize,
127        dependencies: Vec<(Vec<usize>, Vec<usize>)>,
128        query_attribute: usize,
129    ) -> Self {
130        assert!(
131            query_attribute < num_attributes,
132            "Query attribute {} is outside attribute set of size {}",
133            query_attribute,
134            num_attributes
135        );
136        for (i, (lhs, rhs)) in dependencies.iter().enumerate() {
137            assert!(!lhs.is_empty(), "Dependency {} has empty LHS", i);
138            for &attr in lhs.iter().chain(rhs.iter()) {
139                assert!(
140                    attr < num_attributes,
141                    "Dependency {} references attribute {} which is outside attribute set of size {}",
142                    i,
143                    attr,
144                    num_attributes
145                );
146            }
147        }
148        Self {
149            num_attributes,
150            dependencies,
151            query_attribute,
152        }
153    }
154
155    /// Get the number of attributes.
156    pub fn num_attributes(&self) -> usize {
157        self.num_attributes
158    }
159
160    /// Get the number of functional dependencies.
161    pub fn num_dependencies(&self) -> usize {
162        self.dependencies.len()
163    }
164
165    /// Get the query attribute index.
166    pub fn query_attribute(&self) -> usize {
167        self.query_attribute
168    }
169
170    /// Get the functional dependencies.
171    pub fn dependencies(&self) -> &[(Vec<usize>, Vec<usize>)] {
172        &self.dependencies
173    }
174
175    /// Compute the attribute closure of a set under the functional dependencies.
176    ///
177    /// Starting from the given boolean mask of attributes, repeatedly applies
178    /// all functional dependencies until a fixpoint is reached.
179    pub fn compute_closure(&self, attrs: &[bool]) -> Vec<bool> {
180        let mut closure = attrs.to_vec();
181        loop {
182            let mut changed = false;
183            for (lhs, rhs) in &self.dependencies {
184                if lhs.iter().all(|&a| closure[a]) {
185                    for &a in rhs {
186                        if !closure[a] {
187                            closure[a] = true;
188                            changed = true;
189                        }
190                    }
191                }
192            }
193            if !changed {
194                break;
195            }
196        }
197        closure
198    }
199}
200
201impl Problem for PrimeAttributeName {
202    const NAME: &'static str = "PrimeAttributeName";
203    type Solution = Vec<bool>;
204    type Value = crate::types::Or;
205
206    crate::problem_parameters![
207        ("num_attributes", num_attributes),
208        ("num_dependencies", num_dependencies),
209    ];
210
211    fn evaluate(
212        &self,
213        config: &Self::Solution,
214    ) -> Result<crate::types::Or, crate::traits::EvaluationError> {
215        Ok({
216            crate::types::Or({
217                if config.len() != self.num_attributes {
218                    return Err(crate::traits::EvaluationError::InvalidConfiguration(
219                        "attribute-selection length does not match the relation".into(),
220                    ));
221                }
222
223                // query_attribute must be in K
224                if !config[self.query_attribute] {
225                    return Ok(crate::types::Or(false));
226                }
227
228                // Compute closure(K) -- must equal all attributes (K is a superkey)
229                let closure = self.compute_closure(config);
230                if closure.iter().any(|&v| !v) {
231                    return Ok(crate::types::Or(false));
232                }
233
234                // Check minimality: removing any attribute from K must break the superkey property
235                for i in 0..self.num_attributes {
236                    if config[i] {
237                        let mut reduced = config.clone();
238                        reduced[i] = false;
239                        let reduced_closure = self.compute_closure(&reduced);
240                        if reduced_closure.iter().all(|&v| v) {
241                            // K \ {i} is still a superkey, so K is not minimal
242                            return Ok(crate::types::Or(false));
243                        }
244                    }
245                }
246
247                true
248            })
249        })
250    }
251
252    fn variant() -> Vec<(&'static str, &'static str)> {
253        crate::variant_params![]
254    }
255}
256
257impl crate::solvers::BruteForceProblem for PrimeAttributeName {
258    fn dimensions(&self) -> Vec<usize> {
259        vec![2; self.num_attributes]
260    }
261}
262
263crate::declare_variants! {
264    default PrimeAttributeName => "2^num_attributes * num_dependencies * num_attributes" create PrimeAttributeNameCreateSpec,
265}
266
267crate::register_brute_force! {
268    PrimeAttributeName decode |_, indices: Vec<usize>| crate::config::config_to_bits(&indices),
269}
270
271#[cfg(feature = "example-db")]
272pub(crate) fn canonical_model_example_specs() -> Vec<crate::example_db::specs::ModelExampleSpec> {
273    vec![crate::example_db::specs::ModelExampleSpec {
274        id: "prime_attribute_name",
275        // Issue Example 1: 6 attributes, 3 FDs, query=3 -> YES
276        instance: Box::new(PrimeAttributeName::new(
277            6,
278            vec![
279                (vec![0, 1], vec![2, 3, 4, 5]),
280                (vec![2, 3], vec![0, 1, 4, 5]),
281                (vec![0, 3], vec![1, 2, 4, 5]),
282            ],
283            3,
284        )),
285        // {2, 3} is a candidate key containing attribute 3
286        optimal_config: serde_json::json!(vec![false, false, true, true, false, false]),
287        optimal_value: serde_json::json!(true),
288    }]
289}
290
291#[cfg(test)]
292#[path = "../../unit_tests/models/set/prime_attribute_name.rs"]
293mod tests;
problemreductions/models/set/prime_attribute_name.rs

problemreductions/models/set/
prime_attribute_name.rs
