Struct JoinGraph 

pub struct JoinGraph { /* private fields */ }

A join query described precisely enough to bound provably.

See the module documentation for the theorem this implements and for where the degree statistics come from.

Implementations

impl JoinGraph

pub fn new(relations: Vec<JoinRelation>) -> Self

Build a graph over relations, with no predicates yet.

pub fn with_edge( self, left: usize, right: usize, attribute: AttributeId, ) -> Self

Add an equality predicate between two relations on one attribute.

Out-of-range indices and self-edges are dropped: a misbuilt join graph must degrade the ceiling, never corrupt or panic it.

Examples

use samkhya_core::degree::{JoinGraph, JoinRelation};

let g = JoinGraph::new(vec![JoinRelation::new(5), JoinRelation::new(7)])
    .with_edge(0, 1, 0)
    .with_edge(0, 9, 0);   // dropped: index 9 does not exist
assert_eq!(g.edges().len(), 1);

pub fn relations(&self) -> &[JoinRelation]

The relations in this graph.

pub fn edges(&self) -> &[JoinEdge]

The equality predicates in this graph.

pub fn ceiling(&self) -> u64

A provable inclusive ceiling on the join’s output cardinality.

Never returns a value below the true cardinality of any database instance consistent with the supplied statistics, provided every AttributeDegree honours its soundness obligation.

The ceiling is the minimum of the Cartesian product and the spanning-tree degree bound evaluated from every possible root. Because every spanning tree yields a sound ceiling, the search over roots affects only tightness, never correctness.

Examples

use samkhya_core::degree::{AttributeDegree, JoinGraph, JoinRelation};

// Three 3-row relations chained on two attributes, every row on the
// same key: the join really does degenerate to 27 rows, and the
// ceiling says so rather than pretending otherwise.
let rel = |n| JoinRelation::new(n);
let g = JoinGraph::new(vec![rel(3), rel(3), rel(3)])
    .with_edge(0, 1, 0)
    .with_edge(1, 2, 1);
assert_eq!(g.ceiling(), 27);

Trait Implementations

impl Clone for JoinGraph

fn clone(&self) -> JoinGraph

Returns a duplicate of the value.

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

Performs copy-assignment from source.

impl Debug for JoinGraph

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

Formats the value using the given formatter.

impl Default for JoinGraph

fn default() -> JoinGraph

Returns the “default value” for a type.