Browse Prior Art Database

Method for Determining All Predicates And Expressions Implied by Equality Predicates in a Relational Query

IP.com Disclosure Number: IPCOM000100293D
Original Publication Date: 1990-Mar-01
Included in the Prior Art Database: 2005-Mar-15
Document File: 1 page(s) / 46K

Publishing Venue

IBM

Related People

Lohman, GM: AUTHOR [+3]

Abstract

This invention determines all predicates and expressions that are implied by a set of equality predicates in a relational query. For example, the predicates p1:X.a = Y.b and p2:Y.b = Z.c together imply a predicate p3:X.a = Z.c. In addition, for any general expression e(..., X.a, ...), the above equality predicates imply e(..., Y.b, ...) and e(..., Z.c, ...). Note that expression e can be in the list of output expressions (the SELECT list in SQL) as well as in any predicate, including nested subquery or correlation predicates. In all of the above, implications are valid even if a column is equated with a constant, a host variable, or a correlation variable, e.g., adding another given predicate p4:Z.c = 5 implies predicates p5:X.a = 5 and p6:Y.b = 5.

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 68% of the total text.

Method for Determining All Predicates And Expressions Implied by Equality Predicates in a Relational Query

       This invention determines all predicates and expressions
that are implied by a set of equality predicates in a relational
query.  For example, the predicates p1:X.a = Y.b and p2:Y.b = Z.c
together imply a predicate p3:X.a = Z.c. In addition, for any general
expression e(..., X.a, ...), the above equality predicates imply
e(..., Y.b, ...)  and e(..., Z.c, ...).  Note that expression e can
be in the list of output expressions (the SELECT list in SQL) as well
as in any predicate, including nested subquery or correlation
predicates.  In all of the above, implications are valid even if a
column is equated with a constant, a host variable, or a correlation
variable, e.g., adding another given predicate p4:Z.c = 5 implies
predicates p5:X.a = 5 and p6:Y.b = 5.

      Specifically, the method retains as "equivalence classes" all
columns made equal to each other by equality predicates specified by
the user in the query, and chooses one (the first) such column in
each class to be the "representative" of that class to be substituted
for any class member in all subsequent expressions.  In this way,
expressions involving any member of an equivalence class are reduced
to expressions involving representatives of equivalence classes, and
all implied expressions can be generated by replacing the
representative with each member of the class.  In the above example,
p...