Class RexImplicationChecker

  • public class RexImplicationChecker
    extends java.lang.Object
    Checks whether one condition logically implies another.

    If A ⇒ B, whenever A is true, B will be true also.

    For example:

    • (x > 10) ⇒ (x > 5)
    • (x = 10) ⇒ (x < 30 OR y > 30)
    • (x = 10) ⇒ (x IS NOT NULL)
    • (x > 10 AND y = 20) ⇒ (x > 5)
    • Method Detail

      • implies

        public boolean implies​(RexNode first,
                               RexNode second)
        Checks if condition first implies (⇒) condition second.

        This reduces to SAT problem which is NP-Complete. When this method says first implies second then it is definitely true. But it cannot prove that first does not imply second.

        first - first condition
        second - second condition
        true if it can prove first ⇒ second; otherwise false i.e., it doesn't know if implication holds
      • impliesAny

        private boolean impliesAny​(RexNode first,
                                   java.util.List<RexNode> seconds)
        Returns whether the predicate first implies (⇒) at least one predicate in seconds.
      • impliesConjunction

        private boolean impliesConjunction​(RexNode first,
                                           RexNode second)
        Returns whether the predicate first implies second (both may be conjunctions).
      • implies2

        private boolean implies2​(RexNode first,
                                 RexNode second)
        Returns whether the predicate first (not a conjunction) implies second.
      • isSatisfiable

        private boolean isSatisfiable​(RexNode second,
                                      DataContext dataValues)
      • checkSupport

        private boolean checkSupport​(RexImplicationChecker.InputUsageFinder firstUsageFinder,
                                     RexImplicationChecker.InputUsageFinder secondUsageFinder)
        Looks at the usage of variables in first and second conjunction to decide whether this kind of expression is currently supported for proving first implies second.
        1. Variables should be used only once in both the conjunction against given set of operations only: >, <, ≤, ≥, =; ≠.
        2. All the variables used in second condition should be used even in the first.
        3. If operator used for variable in first is op1 and op2 for second, then we support these combination for conjunction (op1, op2) then op1, op2 belongs to one of the following sets:
          • (<, ≤) X (<, ≤) note: X represents cartesian product
          • (> / ≥) X (>, ≥)
          • (=) X (>, ≥, <, ≤, =, ≠)
          • (≠, =)
        4. We support at most 2 operators to be be used for a variable in first and second usages.
        whether input usage pattern is supported
      • isSupportedUnaryOperators

        private boolean isSupportedUnaryOperators​(SqlKind kind)
      • isEquivalentOp

        private boolean isEquivalentOp​(SqlKind fKind,
                                       SqlKind sKind)
      • isOppositeOp

        private boolean isOppositeOp​(SqlKind fKind,
                                     SqlKind sKind)
      • validate

        private boolean validate​(RexNode first,
                                 RexNode second)