Package org.apache.calcite.util

Class ArrowSet

java.lang.Object
org.apache.calcite.util.ArrowSet
public class ArrowSet extends Object
Represents a set of functional dependencies. Each functional dependency is an Arrow.

An ArrowSet models a set of functional dependencies that may hold in a relation. This class provides implementations for several core algorithms in functional dependency theory, such as closure computation and candidate key discovery. For theory background, see: Functional dependency (Wikipedia)

See Also:

  • Field Details

    • EMPTY

      public static final ArrowSet EMPTY

  • Constructor Details

    • ArrowSet

      public ArrowSet(Set<Arrow> arrows)

  • Method Details

    • dependents

      public ImmutableBitSet dependents(ImmutableBitSet ordinals)
      Computes the closure of a given set of column ordinals with respect to this ArrowSet.

      The closure is the maximal set of attributes such that X → X⁺ can be inferred through transitive application of Armstrong's axioms

      Example: 

       // Given functional dependencies:
 // {0} → {1}
 // {1} → {2}
 // dependents(ImmutableBitSet.of(0)) = {0, 1, 2}

      Time complexity: O(m + n), m = arrow count, n = ordinal count. For interactive use, keep n below a few hundred for performance.

      Parameters:
      ordinals - the set of column ordinals whose closure is to be computed
      Returns:
      an immutable set of column ordinals that can be determined from the input

    • determinants

      public Set<ImmutableBitSet> determinants(ImmutableBitSet ordinals)
      Finds all minimal determinant sets for a given set of column ordinals based on this ArrowSet.

      Example: 

      
 // Given functional dependencies:
 // {0} → {1}
 // {1} → {2}
 // {2} → {3}
 // The ordinals is {0, 1, 2, 3}:
 // determinants(ImmutableBitSet.of(0, 1, 2, 3)) returns [{0}]
      Parameters:
      ordinals - a set of attribute ordinals for which to find determinant sets
      Returns:
      the determinant sets, each represented as an ImmutableBitSet

    • union

      public ArrowSet union(ArrowSet other)
      Returns a new ArrowSet that is the union of this and another ArrowSet.

    • getArrows

      public com.google.common.collect.ImmutableList<Arrow> getArrows()
      Returns all arrows (functional dependencies) in this ArrowSet.

    • clone

      public ArrowSet clone()
      Overrides:
      clone in class Object

    • equalTo

      public boolean equalTo(ArrowSet other)

    • toString

      public String toString()
      Overrides:
      toString in class Object

    • implies

      public boolean implies(ImmutableBitSet determinants, ImmutableBitSet dependents)
      Returns true if, from this ArrowSet, one can deduce that determinants determine dependents. That is, if dependents ⊆ closure(determinants).