@techreport{ilprints60,
          number = {1994-26},
          author = {V. Harinarayan and A. Gupta},
       booktitle = {International Conference on Database Theory (ICDT)},
           title = {Optimization Using Tuple Subsumption.},
            type = {Technical Report},
       publisher = {Stanford InfoLab},
     institution = {Stanford Infolab},
            year = {1994},
             url = {http://ilpubs.stanford.edu:8090/60/},
        abstract = {A tuple t 1 of relation R subsumes tuple t 2 of R, with respect to a query Q if for every database, tuple t 1 derives all, and possibly more, answers to query Q than derived by tuple t 2 . Therefore, the subsumed tuple t 2 can be ignored with respect to Q in the presence of tuple t 1 in relation R. This property finds use in a large number of problems. For instance: during query optimization subsumed tuples can be ignored thereby avoiding the computation of redundant answers; the size of cached information in distributed and object oriented systems can be reduced by omitting subsumed tuples; constraints need not be checked and rules need not be recomputed when provably subsumed updates are made. We give algorithms for deciding effciently when a tuple subsumes another tuple for queries that use arbitrary mathematical functions. We characterize queries for which, whenever a set of tuples T subsumes a tuple t then one of the tuples in T also subsumed t, yielding effciently verifiable cases of subsumption.}
}