Struct ConjunctiveQueryFoldability 

pub struct ConjunctiveQueryFoldability { /* private fields */ }

The Conjunctive Query Foldability problem.

Given a finite domain D, a set of relation symbols with fixed arities, distinguished variables X, undistinguished variables Y, and two conjunctive queries Q1 and Q2 (over X ∪ Y ∪ D), this problem asks: does there exist a substitution σ: Y → X ∪ Y ∪ D that maps every atom of Q1 to an atom of Q2?

This is equivalent to the query containment problem for conjunctive queries and is NP-complete (Chandra & Merlin, 1977; Garey & Johnson A4 SR30).

Representation

• Each undistinguished variable Y[i] is a configuration variable whose value encodes its substitution target:
  • 0..domain_size → Constant(v)
  • domain_size..domain_size+num_distinguished → Distinguished(v - domain_size)
  • domain_size+num_distinguished.. → Undistinguished(v - domain_size - num_distinguished)
• The problem is satisfiable iff applying σ to all atoms of Q1 yields exactly the multiset (treated as a set) of atoms in Q2.

Example

use problemreductions::models::misc::{ConjunctiveQueryFoldability, Term};
use problemreductions::{Problem, Solver, BruteForce};

// Q1: R(x, u) ∧ R(u, u)    Q2: R(x, x)  (single atom; duplicates are irrelevant)
// σ: u → x (index = domain_size + 0 = 0) folds Q1 to Q2
let problem = ConjunctiveQueryFoldability::new(
    0, 1, 1,
    vec![2],
    vec![
        (0, vec![Term::Distinguished(0), Term::Undistinguished(0)]),
        (0, vec![Term::Undistinguished(0), Term::Undistinguished(0)]),
    ],
    vec![
        (0, vec![Term::Distinguished(0), Term::Distinguished(0)]),
    ],
);
let solver = BruteForce::new();
let solution = solver.find_witness(&problem);
assert!(solution.is_some());

Implementations

impl ConjunctiveQueryFoldability

pub fn new( domain_size: usize, num_distinguished: usize, num_undistinguished: usize, relation_arities: Vec<usize>, query1_conjuncts: Vec<(usize, Vec<Term>)>, query2_conjuncts: Vec<(usize, Vec<Term>)>, ) -> Self

Create a new ConjunctiveQueryFoldability instance.

Arguments

• domain_size – Number of domain constants |D|.
• num_distinguished – Number of distinguished variables |X|.
• num_undistinguished – Number of undistinguished variables |Y|.
• relation_arities – Arity of each relation symbol.
• query1_conjuncts – Atoms of Q1 as (relation_index, args) pairs.
• query2_conjuncts – Atoms of Q2 as (relation_index, args) pairs.

Panics

Panics if:

• Any atom references a relation index out of range.
• Any atom has the wrong number of arguments for its relation’s arity.
• Any Constant(i) has i >= domain_size.
• Any Distinguished(i) has i >= num_distinguished.
• Any Undistinguished(i) has i >= num_undistinguished.

pub fn domain_size(&self) -> usize

Returns the size of the finite domain D.

pub fn num_distinguished(&self) -> usize

Returns the number of distinguished variables X.

pub fn num_undistinguished(&self) -> usize

Returns the number of undistinguished variables Y.

pub fn num_conjuncts_q1(&self) -> usize

Returns the number of conjuncts (atoms) in Q1.

pub fn num_conjuncts_q2(&self) -> usize

Returns the number of conjuncts (atoms) in Q2.

pub fn num_relations(&self) -> usize

Returns the number of relation symbols.

pub fn relation_arities(&self) -> &[usize]

Returns the arities of the relation symbols.

pub fn query1_conjuncts(&self) -> &[(usize, Vec<Term>)]

Returns the atoms (conjuncts) of query Q1.

pub fn query2_conjuncts(&self) -> &[(usize, Vec<Term>)]

Returns the atoms (conjuncts) of query Q2.

Trait Implementations

impl Clone for ConjunctiveQueryFoldability

fn clone(&self) -> ConjunctiveQueryFoldability

Returns a duplicate of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl Debug for ConjunctiveQueryFoldability

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl<'de> Deserialize<'de> for ConjunctiveQueryFoldability

fn deserialize<__D>(__deserializer: __D) -> Result<Self, __D::Error>

where __D: Deserializer<'de>,

Deserialize this value from the given Serde deserializer.

impl Problem for ConjunctiveQueryFoldability

fn dims(&self) -> Vec<usize>

Returns the configuration space dimensions.

Each of the num_undistinguished variables can map to any element of D ∪ X ∪ Y, giving domain_size + num_distinguished + num_undistinguished choices per variable. When num_undistinguished == 0 the vector is empty (Q1 contains no variables to substitute; the problem is trivially decided by checking set equality of Q1 and Q2 at evaluation time).

fn evaluate(&self, config: &[usize]) -> Or

Evaluate whether configuration config represents a folding of Q1 into Q2.

Returns true iff applying the substitution encoded by config to every atom of Q1 produces exactly the set of atoms in Q2.

const NAME: &'static str = "ConjunctiveQueryFoldability"

Base name of this problem type (e.g., “MaximumIndependentSet”).

type Value = Or

The evaluation value type.

fn variant() -> Vec<(&'static str, &'static str)>

Returns variant attributes derived from type parameters.

fn num_variables(&self) -> usize

Number of variables (derived from dims).

fn problem_type() -> ProblemType

Look up this problem’s catalog entry.

impl Serialize for ConjunctiveQueryFoldability

fn serialize<__S>(&self, __serializer: __S) -> Result<__S::Ok, __S::Error>

where __S: Serializer,

Serialize this value into the given Serde serializer.

impl DeclaredVariant for ConjunctiveQueryFoldability