Graph-based synopses for relational selectivity estimation
Authors:
Open Access
- 27 June 2006
- conference paper
- Published by Association for Computing Machinery (ACM)
- p. 205-216
Abstract
This paper introduces the Tuple Graph (TUG) synopses, a new class of data summaries that enable accurate selectivity estimates for complex relational queries. The proposed summarization framework adopts a "semi-structured" view of the relational database, modeling a relational data set as a graph of tuples and join queries as graph traversals respectively. The key idea is to approximate the structure of the induced data graph in a concise synopsis, and to estimate the selectivity of a query by performing the corresponding traversal over the summarized graph. We detail the TUG synopsis model that is based on this novel approach, and we describe an efficient and scalable construction algorithm for building accurate TUGs within a specific storage budget. We validate the performance of TUGs with an extensive experimental study on real-life and synthetic data sets. Our results verify the effectiveness of TUGs in generating accurate selectivity estimates for complex join queries, and demonstrate their benefits over existing summarization techniques.Keywords
This publication has 15 references indexed in Scilit:
- An improved data stream summary: the count-min sketch and its applicationsJournal of Algorithms, 2005
- Approximate XML query answers2004
- Processing complex aggregate queries over data streams2002
- Independence is good2001
- Selectivity estimation using probabilistic models2001
- Join synopses for approximate query answering1999
- On random sampling over joins1999
- Self-tuning histograms1999
- BIRCH1996
- Efficient sampling strategies for relational database operationsTheoretical Computer Science, 1993