Harinarayan, V. and Gupta, A. (1994) *Optimization Using Tuple Subsumption.* Technical Report. Stanford InfoLab. (Publication Note: Appeared in 5th International Conference on Database Theory, Prague, Czech Republic, January 11-13, 1995 (ICDT 1995))

BibTeX | DublinCore | EndNote | HTML |

| PDF 193Kb |

## 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.

Item Type: | Techreport (Technical Report) | |
---|---|---|

Subjects: | Computer Science > Query Processing | |

Projects: | Information Integration | |

Related URLs: | Project Homepage | http://infolab.stanford.edu/serf/ |

ID Code: | 60 | |

Deposited By: | Import Account | |

Deposited On: | 25 Feb 2000 16:00 | |

Last Modified: | 05 Feb 2009 15:35 |

## Download statistics

Repository Staff Only: item control page