problemreductions/models/misc/
conjunctive_boolean_query.rs

1//! Conjunctive Boolean Query problem implementation.
2//!
3//! Given a finite domain `D = {0, ..., domain_size-1}`, a collection of
4//! relations `R`, and a conjunctive Boolean query
5//! `Q = (exists y_1, ..., y_l)(A_1 /\ ... /\ A_r)`, determine whether `Q` is
6//! true over `R` and `D`.
7//!
8//! Each conjunct `A_i` applies a relation to a tuple of arguments, where each
9//! argument is either an existentially quantified variable or a constant from
10//! the domain. The query is satisfiable iff there exists an assignment to the
11//! variables such that every conjunct's resolved tuple belongs to its relation.
12
13use crate::registry::{FieldInfo, ProblemSchemaEntry};
14use crate::traits::Problem;
15use serde::{Deserialize, Serialize};
16
17inventory::submit! {
18    ProblemSchemaEntry {
19        name: "ConjunctiveBooleanQuery",
20        display_name: "Conjunctive Boolean Query",
21        aliases: &["CBQ"],
22        dimensions: &[],
23        module_path: module_path!(),
24        description: "Evaluate a conjunctive Boolean query over a relational database",
25        fields: &[
26            FieldInfo { name: "domain_size", type_name: "usize", description: "Size of the finite domain D" },
27            FieldInfo { name: "relations", type_name: "Vec<Relation>", description: "Collection of relations R" },
28            FieldInfo { name: "num_variables", type_name: "usize", description: "Number of existentially quantified variables" },
29            FieldInfo { name: "conjuncts", type_name: "Vec<(usize, Vec<QueryArg>)>", description: "Query conjuncts: (relation_index, arguments)" },
30        ],
31    }
32}
33
34/// A relation with fixed arity and a set of tuples over a finite domain.
35#[derive(Debug, Clone, PartialEq, Serialize, Deserialize)]
36pub struct Relation {
37    /// The arity (number of columns) of this relation.
38    pub arity: usize,
39    /// The set of tuples; each tuple has length == arity, entries in `0..domain_size`.
40    pub tuples: Vec<Vec<usize>>,
41}
42
43/// An argument in a conjunctive query atom.
44#[derive(Debug, Clone, PartialEq, Serialize, Deserialize)]
45pub enum QueryArg {
46    /// A reference to existential variable `y_i` (0-indexed).
47    Variable(usize),
48    /// A constant value from the domain `D`.
49    Constant(usize),
50}
51
52/// The Conjunctive Boolean Query problem.
53///
54/// Given a finite domain `D = {0, ..., domain_size-1}`, a collection of
55/// relations `R`, and a conjunctive Boolean query
56/// `Q = (exists y_1, ..., y_l)(A_1 /\ ... /\ A_r)`, determine whether `Q` is
57/// true over `R` and `D`.
58///
59/// # Representation
60///
61/// The configuration is a vector of length `num_variables`, where each entry is
62/// a value in `{0, ..., domain_size-1}` representing an assignment to the
63/// existentially quantified variables.
64///
65/// # Example
66///
67/// ```
68/// use problemreductions::models::misc::{ConjunctiveBooleanQuery, CbqRelation, QueryArg};
69/// use problemreductions::{Problem, Solver, BruteForce};
70///
71/// let relations = vec![
72///     CbqRelation { arity: 2, tuples: vec![vec![0, 3], vec![1, 3]] },
73/// ];
74/// let conjuncts = vec![
75///     (0, vec![QueryArg::Variable(0), QueryArg::Constant(3)]),
76/// ];
77/// let problem = ConjunctiveBooleanQuery::new(6, relations, 1, conjuncts);
78/// let solver = BruteForce::new();
79/// let solution = solver.find_witness(&problem);
80/// assert!(solution.is_some());
81/// ```
82#[derive(Debug, Clone, PartialEq, Serialize, Deserialize)]
83pub struct ConjunctiveBooleanQuery {
84    domain_size: usize,
85    relations: Vec<Relation>,
86    num_variables: usize,
87    conjuncts: Vec<(usize, Vec<QueryArg>)>,
88}
89
90impl ConjunctiveBooleanQuery {
91    /// Create a new ConjunctiveBooleanQuery instance.
92    ///
93    /// # Panics
94    ///
95    /// Panics if:
96    /// - Any relation's tuples have incorrect arity
97    /// - Any tuple entry is >= domain_size
98    /// - Any conjunct references a non-existent relation
99    /// - Any `Variable(i)` has `i >= num_variables`
100    /// - Any `Constant(c)` has `c >= domain_size`
101    /// - Any conjunct's argument count does not match the referenced relation's arity
102    pub fn new(
103        domain_size: usize,
104        relations: Vec<Relation>,
105        num_variables: usize,
106        conjuncts: Vec<(usize, Vec<QueryArg>)>,
107    ) -> Self {
108        for (i, rel) in relations.iter().enumerate() {
109            for (j, tuple) in rel.tuples.iter().enumerate() {
110                assert!(
111                    tuple.len() == rel.arity,
112                    "Relation {i}: tuple {j} has length {}, expected arity {}",
113                    tuple.len(),
114                    rel.arity
115                );
116                for (k, &val) in tuple.iter().enumerate() {
117                    assert!(
118                        val < domain_size,
119                        "Relation {i}: tuple {j}, entry {k} is {val}, must be < {domain_size}"
120                    );
121                }
122            }
123        }
124        for (i, (rel_idx, args)) in conjuncts.iter().enumerate() {
125            assert!(
126                *rel_idx < relations.len(),
127                "Conjunct {i}: relation index {rel_idx} out of range (have {} relations)",
128                relations.len()
129            );
130            assert!(
131                args.len() == relations[*rel_idx].arity,
132                "Conjunct {i}: has {} args, expected arity {}",
133                args.len(),
134                relations[*rel_idx].arity
135            );
136            for (k, arg) in args.iter().enumerate() {
137                match arg {
138                    QueryArg::Variable(v) => {
139                        assert!(
140                            *v < num_variables,
141                            "Conjunct {i}, arg {k}: Variable({v}) >= num_variables ({num_variables})"
142                        );
143                    }
144                    QueryArg::Constant(c) => {
145                        assert!(
146                            *c < domain_size,
147                            "Conjunct {i}, arg {k}: Constant({c}) >= domain_size ({domain_size})"
148                        );
149                    }
150                }
151            }
152        }
153        Self {
154            domain_size,
155            relations,
156            num_variables,
157            conjuncts,
158        }
159    }
160
161    /// Returns the size of the finite domain.
162    pub fn domain_size(&self) -> usize {
163        self.domain_size
164    }
165
166    /// Returns the number of relations.
167    pub fn num_relations(&self) -> usize {
168        self.relations.len()
169    }
170
171    /// Returns the number of existentially quantified variables.
172    pub fn num_variables(&self) -> usize {
173        self.num_variables
174    }
175
176    /// Returns the number of conjuncts in the query.
177    pub fn num_conjuncts(&self) -> usize {
178        self.conjuncts.len()
179    }
180
181    /// Returns the relations.
182    pub fn relations(&self) -> &[Relation] {
183        &self.relations
184    }
185
186    /// Returns the conjuncts.
187    pub fn conjuncts(&self) -> &[(usize, Vec<QueryArg>)] {
188        &self.conjuncts
189    }
190}
191
192impl Problem for ConjunctiveBooleanQuery {
193    const NAME: &'static str = "ConjunctiveBooleanQuery";
194    type Value = crate::types::Or;
195
196    fn variant() -> Vec<(&'static str, &'static str)> {
197        crate::variant_params![]
198    }
199
200    fn dims(&self) -> Vec<usize> {
201        vec![self.domain_size; self.num_variables]
202    }
203
204    fn evaluate(&self, config: &[usize]) -> crate::types::Or {
205        crate::types::Or({
206            if config.len() != self.num_variables {
207                return crate::types::Or(false);
208            }
209            if config.iter().any(|&v| v >= self.domain_size) {
210                return crate::types::Or(false);
211            }
212            self.conjuncts.iter().all(|(rel_idx, args)| {
213                let tuple: Vec<usize> = args
214                    .iter()
215                    .map(|arg| match arg {
216                        QueryArg::Variable(i) => config[*i],
217                        QueryArg::Constant(c) => *c,
218                    })
219                    .collect();
220                self.relations[*rel_idx].tuples.contains(&tuple)
221            })
222        })
223    }
224}
225
226crate::declare_variants! {
227    default ConjunctiveBooleanQuery => "domain_size ^ num_variables",
228}
229
230#[cfg(feature = "example-db")]
231pub(crate) fn canonical_model_example_specs() -> Vec<crate::example_db::specs::ModelExampleSpec> {
232    vec![crate::example_db::specs::ModelExampleSpec {
233        id: "conjunctive_boolean_query",
234        // D={0..5}, 2 relations (binary R0, ternary R1), 3 atoms, 2 variables.
235        // Satisfying assignment: y0=0, y1=1.
236        instance: Box::new(ConjunctiveBooleanQuery::new(
237            6,
238            vec![
239                Relation {
240                    arity: 2,
241                    tuples: vec![vec![0, 3], vec![1, 3], vec![2, 4], vec![3, 4], vec![4, 5]],
242                },
243                Relation {
244                    arity: 3,
245                    tuples: vec![vec![0, 1, 5], vec![1, 2, 5], vec![2, 3, 4], vec![0, 4, 3]],
246                },
247            ],
248            2,
249            vec![
250                (0, vec![QueryArg::Variable(0), QueryArg::Constant(3)]),
251                (0, vec![QueryArg::Variable(1), QueryArg::Constant(3)]),
252                (
253                    1,
254                    vec![
255                        QueryArg::Variable(0),
256                        QueryArg::Variable(1),
257                        QueryArg::Constant(5),
258                    ],
259                ),
260            ],
261        )),
262        optimal_config: vec![0, 1],
263        optimal_value: serde_json::json!(true),
264    }]
265}
266
267#[cfg(test)]
268#[path = "../../unit_tests/models/misc/conjunctive_boolean_query.rs"]
269mod tests;
problemreductions/models/misc/conjunctive_boolean_query.rs

problemreductions/models/misc/
conjunctive_boolean_query.rs
