Struct FunctionalDependencySet

pub struct FunctionalDependencySet {
    column_count: usize,
    strict: Vec<FunctionalDependency>,
}

FunctionalDependencySet contains the functional dependencies.

It is used in optimizer to track the dependencies between columns.

Fields

column_count: usize

the number of columns

strict: Vec<FunctionalDependency>

strict contains all strict functional dependencies.

The strict functional dependency use the NULL= semantic. It means that all NULLs are considered as equal. So for following table, A –> B is not valid. NOT allowed.

  A   | B
------|---
 NULL | 1
 NULL | 2

Currently we only have strict dependencies, but we may also have lax dependencies in the future.

Implementations

impl FunctionalDependencySet

pub fn new(column_count: usize) -> Self

Create an empty FunctionalDependencySet

pub fn with_key(column_cnt: usize, key_indices: &[usize]) -> Self

Create a FunctionalDependencySet with the indices of a key.

The combination of these columns can determine all other columns.

pub fn with_dependencies( column_count: usize, strict_dependencies: Vec<FunctionalDependency>, ) -> Self

Create a FunctionalDependencySet with a dependency Vec

pub fn as_dependencies_mut(&mut self) -> &mut Vec<FunctionalDependency>

pub fn as_dependencies(&self) -> &Vec<FunctionalDependency>

pub fn into_dependencies(self) -> Vec<FunctionalDependency>

pub fn add_functional_dependency(&mut self, fd: FunctionalDependency)

Add a functional dependency to a FunctionalDependencySet.

pub fn add_key(&mut self, key_indices: &[usize])

Add key columns to a FunctionalDependencySet.

pub fn add_constant_columns(&mut self, constant_columns: &[usize])

Add constant columns to a FunctionalDependencySet.

pub fn add_functional_dependency_by_column_indices( &mut self, from: &[usize], to: &[usize], )

Add a dependency to FunctionalDependencySet using column indices.

fn get_closure(&self, columns: &FixedBitSet) -> FixedBitSet

O(d), where d is the number of functional dependencies. The call to is_subset is technically O(n), but we can consider it O(1) since the constant factor is 1/usize.

pub fn is_determined_by( &self, determinant: &FixedBitSet, dependant: &FixedBitSet, ) -> bool

Return true if the dependency determinant -> dependant exists. O(d), where the dominant cost is from Self::get_closure, which has O(d) complexity.

fn is_key_inner(&self, columns: &FixedBitSet) -> bool

This just checks if the columns specified by the columns bitset determines each other column.

pub fn is_key(&self, columns: &[usize]) -> bool

Return true if the combination of columns can fully determine other columns.

pub fn minimize_key(&self, key_indices: &[usize]) -> Vec<usize>

This is just a wrapper around Self::minimize_key_bitset to minimize key_indices.

fn minimize_key_bitset(&self, key: FixedBitSet) -> FixedBitSet

---

Overview

Remove redundant columns from the given set.

Redundant columns can be functionally determined by other columns so there is no need to keep them in a key.

Note that the accurate minimization algorithm can take O(2^n) time, so we use a approximate algorithm which use O(cn) time. c is the number of columns, and n is the number of functional dependency rules.

This algorithm may not necessarily find the key with the least number of columns. But it will ensure that no redundant columns will be preserved.

---

Algorithm

This algorithm removes columns one by one and check whether the remaining columns can form a key or not. If the remaining columns can form a key, then this column can be removed.

pub fn minimize_order_key( &self, order_key: Order, dist_key_indices: &[usize], ) -> Order

Wrapper around Self::minimize_order_key_bitset to minimize order_key. View the documentation of Self::minimize_order_key_bitset for more information. In the process of minimizing the order key, we must ensure that if the indices are part of distribution key, they must not be pruned.

fn minimize_order_key_bitset(&self, order_key: Vec<usize>) -> FixedBitSet

1. Iterate over the prefixes of the order key.
2. If some continuous subset of columns and the next column of the order key form a functional dependency, we can prune that column.
3. This function has O(dn) complexity, where: i. d is the number of functional dependencies, because each iteration in the loop calls Self::is_determined_by. ii. n is the number of columns.

Trait Implementations

impl Clone for FunctionalDependencySet

fn clone(&self) -> FunctionalDependencySet

Returns a copy of the value.

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

Performs copy-assignment from source.

impl Debug for FunctionalDependencySet

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

Formats the value using the given formatter.

impl Default for FunctionalDependencySet

fn default() -> FunctionalDependencySet

Returns the “default value” for a type.

impl Display for FunctionalDependencySet

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

Formats the value using the given formatter.

impl Hash for FunctionalDependencySet

fn hash<__H: Hasher>(&self, state: &mut __H)

Feeds this value into the given Hasher.

fn hash_slice<H>(data: &[Self], state: &mut H)

where H: Hasher, Self: Sized,

Feeds a slice of this type into the given Hasher.

impl PartialEq for FunctionalDependencySet

fn eq(&self, other: &FunctionalDependencySet) -> bool

Tests for self and other values to be equal, and is used by ==.

fn ne(&self, other: &Rhs) -> bool

Tests for !=. The default implementation is almost always sufficient, and should not be overridden without very good reason.

impl Eq for FunctionalDependencySet

impl StructuralPartialEq for FunctionalDependencySet