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)]
63#[serde(try_from = "PrimeAttributeNameData")]
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
73#[derive(Deserialize)]
74struct PrimeAttributeNameData {
75    num_attributes: usize,
76    dependencies: Vec<(Vec<usize>, Vec<usize>)>,
77    query_attribute: usize,
78}
79
80impl TryFrom<PrimeAttributeNameData> for PrimeAttributeName {
81    type Error = crate::registry::ConstructionError;
82
83    fn try_from(data: PrimeAttributeNameData) -> Result<Self, Self::Error> {
84        Self::try_new(data.num_attributes, data.dependencies, data.query_attribute)
85    }
86}
87
88#[derive(Debug, Deserialize, crate::CreateSpec)]
89struct PrimeAttributeNameCreateSpec {
90    /// Number of attributes.
91    universe_size: usize,
92    /// Functional dependencies (lhs, rhs) pairs.
93    dependencies: Vec<(Vec<usize>, Vec<usize>)>,
94    /// The query attribute index.
95    query_attribute: usize,
96}
97
98impl TryFrom<PrimeAttributeNameCreateSpec> for PrimeAttributeName {
99    type Error = crate::registry::ConstructionError;
100
101    fn try_from(spec: PrimeAttributeNameCreateSpec) -> Result<Self, Self::Error> {
102        Self::try_new(spec.universe_size, spec.dependencies, spec.query_attribute)
103    }
104}
105
106impl PrimeAttributeName {
107    /// Create a new Prime Attribute Name problem.
108    ///
109    /// # Panics
110    ///
111    /// Panics if `query_attribute >= num_attributes`, if any attribute index
112    /// in a dependency is out of range, or if any LHS is empty.
113    pub fn new(
114        num_attributes: usize,
115        dependencies: Vec<(Vec<usize>, Vec<usize>)>,
116        query_attribute: usize,
117    ) -> Self {
118        Self::try_new(num_attributes, dependencies, query_attribute)
119            .unwrap_or_else(|error| panic!("{error}"))
120    }
121
122    fn try_new(
123        num_attributes: usize,
124        dependencies: Vec<(Vec<usize>, Vec<usize>)>,
125        query_attribute: usize,
126    ) -> Result<Self, crate::registry::ConstructionError> {
127        if query_attribute >= num_attributes {
128            return Err(format!("Query attribute {query_attribute} is outside attribute set of size {num_attributes}").into());
129        }
130        for (index, (lhs, rhs)) in dependencies.iter().enumerate() {
131            if lhs.is_empty() {
132                return Err(format!("Dependency {index} has empty LHS").into());
133            }
134            if let Some(attribute) = lhs
135                .iter()
136                .chain(rhs.iter())
137                .find(|&&attribute| attribute >= num_attributes)
138            {
139                return Err(format!("dependency {index} contains attribute {attribute} outside attribute set of size {num_attributes}").into());
140            }
141        }
142        Ok(Self {
143            num_attributes,
144            dependencies,
145            query_attribute,
146        })
147    }
148
149    /// Get the number of attributes.
150    pub fn num_attributes(&self) -> usize {
151        self.num_attributes
152    }
153
154    /// Get the number of functional dependencies.
155    pub fn num_dependencies(&self) -> usize {
156        self.dependencies.len()
157    }
158
159    /// Get the query attribute index.
160    pub fn query_attribute(&self) -> usize {
161        self.query_attribute
162    }
163
164    /// Get the functional dependencies.
165    pub fn dependencies(&self) -> &[(Vec<usize>, Vec<usize>)] {
166        &self.dependencies
167    }
168
169    /// Compute the attribute closure of a set under the functional dependencies.
170    ///
171    /// Starting from the given boolean mask of attributes, repeatedly applies
172    /// all functional dependencies until a fixpoint is reached.
173    pub fn compute_closure(&self, attrs: &[bool]) -> Vec<bool> {
174        let mut closure = attrs.to_vec();
175        loop {
176            let mut changed = false;
177            for (lhs, rhs) in &self.dependencies {
178                if lhs.iter().all(|&a| closure[a]) {
179                    for &a in rhs {
180                        if !closure[a] {
181                            closure[a] = true;
182                            changed = true;
183                        }
184                    }
185                }
186            }
187            if !changed {
188                break;
189            }
190        }
191        closure
192    }
193}
194
195impl Problem for PrimeAttributeName {
196    const NAME: &'static str = "PrimeAttributeName";
197    type Solution = Vec<bool>;
198    type Value = crate::types::Or;
199
200    crate::problem_parameters![
201        ("num_attributes", num_attributes),
202        ("num_dependencies", num_dependencies),
203    ];
204
205    fn evaluate(
206        &self,
207        config: &Self::Solution,
208    ) -> Result<crate::types::Or, crate::traits::EvaluationError> {
209        Ok({
210            crate::types::Or({
211                if config.len() != self.num_attributes {
212                    return Err(crate::traits::EvaluationError::InvalidConfiguration(
213                        "attribute-selection length does not match the relation".into(),
214                    ));
215                }
216
217                // query_attribute must be in K
218                if !config[self.query_attribute] {
219                    return Ok(crate::types::Or(false));
220                }
221
222                // Compute closure(K) -- must equal all attributes (K is a superkey)
223                let closure = self.compute_closure(config);
224                if closure.iter().any(|&v| !v) {
225                    return Ok(crate::types::Or(false));
226                }
227
228                // Check minimality: removing any attribute from K must break the superkey property
229                for i in 0..self.num_attributes {
230                    if config[i] {
231                        let mut reduced = config.clone();
232                        reduced[i] = false;
233                        let reduced_closure = self.compute_closure(&reduced);
234                        if reduced_closure.iter().all(|&v| v) {
235                            // K \ {i} is still a superkey, so K is not minimal
236                            return Ok(crate::types::Or(false));
237                        }
238                    }
239                }
240
241                true
242            })
243        })
244    }
245
246    fn variant() -> Vec<(&'static str, &'static str)> {
247        crate::variant_params![]
248    }
249}
250
251impl crate::solvers::BruteForceProblem for PrimeAttributeName {
252    fn dimensions(&self) -> Vec<usize> {
253        vec![2; self.num_attributes]
254    }
255}
256
257crate::declare_variants! {
258    default PrimeAttributeName => "2^num_attributes * num_dependencies * num_attributes" create PrimeAttributeNameCreateSpec,
259}
260
261crate::register_brute_force! {
262    PrimeAttributeName decode |_, indices: Vec<usize>| crate::config::config_to_bits(&indices),
263}
264
265#[cfg(feature = "example-db")]
266pub(crate) fn canonical_model_example_specs() -> Vec<crate::example_db::specs::ModelExampleSpec> {
267    vec![crate::example_db::specs::ModelExampleSpec {
268        id: "prime_attribute_name",
269        // Issue Example 1: 6 attributes, 3 FDs, query=3 -> YES
270        instance: Box::new(PrimeAttributeName::new(
271            6,
272            vec![
273                (vec![0, 1], vec![2, 3, 4, 5]),
274                (vec![2, 3], vec![0, 1, 4, 5]),
275                (vec![0, 3], vec![1, 2, 4, 5]),
276            ],
277            3,
278        )),
279        // {2, 3} is a candidate key containing attribute 3
280        optimal_config: serde_json::json!(vec![false, false, true, true, false, false]),
281        optimal_value: serde_json::json!(true),
282    }]
283}
284
285#[cfg(test)]
286#[path = "../../unit_tests/models/set/prime_attribute_name.rs"]
287mod tests;
problemreductions/models/set/prime_attribute_name.rs

problemreductions/models/set/
prime_attribute_name.rs
