Developing a Dynamic Materialized View Index for Efficiently Discovering Usable Views for Progressive Queries
2
조회
0
다운로드
0
인용
0
참고문헌
키워드
초록
Numerous data intensive applications demand the efficient processing of a new type of query, which is called a progressive query (PQ). A PQ consists of a set of unpredictable but inter-related step-queries (SQ) that are specified by its user in a sequence of steps. A conventional DBMS was not designed to efficiently process such PQs. In our earlier work, we introduced a materialized view based approach for efficiently processing PQs, where the focus was on selecting promising views for materialization. The problem of how to efficiently find usable views from the materialized set in order to answer the SQs for a PQ remains open. In this paper, we present a new index technique, called the Dynamic Materialized View Index (DMVI), to rapidly discover usable views for answering a given SQ. The structure of the proposed index is a special ordered tree where the SQ domain tables are used as search keys and some bitmaps are kept at the leaf nodes for refined filtering. A two-level priority rule is adopted to order domain tables in the tree, which facilitates the efficient maintenance of the tree by taking into account the dynamic characteristics of various types of materialized views for PQs. The bitmap encoding methods and the strategies/algorithms to construct, search, and maintain the DMVI are suggested. The extensive experimental results demonstrate that our index technique is quite promising in improving the performance of the materialized view based query processing approach for PQs.
Abstract
Numerous data intensive applications demand the efficient processing of a new type of query, which is called a progressive query (PQ). A PQ consists of a set of unpredictable but inter-related step-queries (SQ) that are specified by its user in a sequence of steps. A conventional DBMS was not designed to efficiently process such PQs. In our earlier work, we introduced a materialized view based approach for efficiently processing PQs, where the focus was on selecting promising views for materialization. The problem of how to efficiently find usable views from the materialized set in order to answer the SQs for a PQ remains open. In this paper, we present a new index technique, called the Dynamic Materialized View Index (DMVI), to rapidly discover usable views for answering a given SQ. The structure of the proposed index is a special ordered tree where the SQ domain tables are used as search keys and some bitmaps are kept at the leaf nodes for refined filtering. A two-level priority rule is adopted to order domain tables in the tree, which facilitates the efficient maintenance of the tree by taking into account the dynamic characteristics of various types of materialized views for PQs. The bitmap encoding methods and the strategies/algorithms to construct, search, and maintain the DMVI are suggested. The extensive experimental results demonstrate that our index technique is quite promising in improving the performance of the materialized view based query processing approach for PQs.
참고문헌 (49)
- S. Agrawal, "Automated selection of materialized views and index-es in SQL databases", roc.of VLDB Conf, pp.391~398 (2000)
- K. Aouiche, "Data mining-based materialized view and index selection in data warehouses", J. Intell. Inf. Syst, 33(1), pp.65~93 (2009)
- L. Bellatreche, "Evaluation of Materialized View Indexing in Data Ware-housing Environments", Proc.of DaWaK Conf, pp.57~66 (2000)
- S. Berchtold, "The X-tree: An Index Structure for High Dimensional Data", Proc.of VLDB Conf, pp.28~39 (1996)
- D. Calvanese, "View-based query process: on therelationship between rewriting, answering and losslessness", Theor.Comput.Sci, 371(3), pp.169~182 (2007)
- K. Chakrabarti, "The Hybrid Tree: An Index Structure for High Dimensional Feature Spaces", Proc.of ICDE Conf, pp.440~447 (1999)
- C. Y. Chan, "RE-Tree: An Efficient Index Structure for Regular Expressions", Proc.of VLDB Conf, pp.263~274 (2002)
- C. Y. Chan, "Bitmap Index Design and Evaluation", Proc.of SIGMOD Conf, pp.355~366 (1998)
- D. Comer, "The ubiquitous B-tree", ACM Computing Survey, 11(2), pp.121~137 (1979)
- F. Fusco, "Real-time creation of bitmap indexes on streaming network data", The VLDB Journal, 21(3), pp.287~307 (2012)
- G. Gou, "Query evaluation using overlapping views: completeness and efficiency", Proc.of SIGMOD Conf, pp.37~48 (2006)
- G. Graefe, "Transaction support for indexed views", Proc. of SIGMOD Conf (2004)
- A. Guttman, "R-Trees: A Dynamic Index Structure for Spatial Searching", Proc.of SIGMOND Conf, pp.47~57 (1984)
- A. Y. Halevy, "Answering queries using views : a survey", The VLDB Journal, 10(4), pp.270~294 (2001)
- H. He, "Closure-Tree: An Index Structure for Graph Queries", Proc.of ICDE Conf, pp.38~ (2006)
- B. He, "Efficient Iceberg Query Evaluation Using Com-pressed Bitmap Index", IEEE Trans. Knowl. Data Eng, 24(9), pp.1570~1583 (2012)
- G. Himanshu, "Selection of Views to Materialize in a Data Warehouse", IEEE Transaction on Knowledge and Data Engineering, 17(1), pp.24~43 (2005)
- H. Jiang, "XR-Tree: Indexing XML Data for Efficient Structural Joins", Proc.of ICDE Conf, pp.253~264 (2003)
- N. Katayama, "The SR-tree: An Index Structure for High-Dimensional Nearest Neighbor Queries", Proc.of SIGMOND Conf, pp.369~380 (1997)
- H. Kimura, "CORADD: Correlation Aware Database Designer for Materialized Views and Indexes", PVLDB, 3(1), pp.1103~1113 (2010)
- H. Kuno, A, "Deferred Maintenance of Indexes and of Materialized Views", Proc. of DNIS Conf, pp.312~323 (2011)
- T. W. Kuo, "Real-Time Data Access Control on B-Tree Index Structures", Proc.of ICDE Conf, pp.458~467 (1999)
- P.-A. Larson, "Computing queries from derived relations", Proc. of VLDB Conf, pp.259~269 (1985)
- P.-A. Larson, "View matching for outer-join views", VLDB Journal, pp.29~53 (2007)
- W. Lehner, "Fast Refesh using Mass Query Op-timization", Proc.of ICDE Conf, pp.391~398 (2001)
- Z. Liu, "Answering Keyword Queries on XML Using Materialized Views", Proc. of ICDE Conf, pp.1501~1503 (2008)
- I. Nitsos, "Bitmap-Tree Indexing for Set Operations on Free Text", Proc.of ICDE Conf, pp.837~ (2004)
- C.-S. Park, "Rewriting OLAP Queries Using Materialized Views and Di-mension Hierarchies in Data Warehouses", Proc. of ICDE Conf, pp.515~523 (2001)
- R. Pottinger, "A Scalable Algorithm for Answering Queries Using Views", Proc. of VLDB Conf, pp.484~495 (2000)
- J.T. Robinson, "The K-D-B-Tree: A Search Structure For Large Multidimensional Dynamic Index-es", Proc. of SIGMOND Conf, pp.10~18 (1981)
- N. Roussopoulos, "View indexing in relational databases", ACM Trans. on Database Systems, 7(2), pp.258~290 (1982)
- P. Roy, "Materialized View Selection and Maintenance Using MultiQuery Optimization Hoshi Mistry", Proc. of SIGMOD Conf, pp.307~318 (2001)
- M. Sadoghi, "BE-tree: an index structure to efficiently match boolean expres-sions over high-dimensional discrete space", Proc.of SIGMOND Conf, pp.637~648 (2011)
- Y. Sakurai, "The A-tree: An Index Structure for High-Dimensional Spaces Using Relative Approximation", Proc.of VLDB Conf, pp.516~526 (2000)
- R. R. Sinha, "Adaptive Bitmap Indexes for Space-Constrained Systems", Proc.of ICDE Conf, pp.1418~1420 (2008)
- H. H. Sinha, "Multi-resolution bitmap indexes for scientific data", ACM Trans. Da-tabase Syst, 32(3), pp.16~ (2010)
- D. Srivastava, "Answering Queries with Aggregation Using Views", Proc.of VLDB Conf, pp.318~329 (1996)
- Z. A. Talebi, "Exact and inexact methods for selecting views and indexes for OLAP performance improvement", Proc. of EDBT Conf, pp.311~322 (2008)
- W. Xu, "Rewriting XPath Queries Using Materialized Views", Proc. of VLDB Conf, pp.121~132 (2005)
- H. Wang, "ViST: A Dynamic Index Method for Querying XML Data by Tree Structures", Proc.of SIGMOND Conf, pp.110~121 (2003)
- H. Wang, "On the Sequencing of Tree Structures for XML Indexing", Proc.of ICDE Conf, pp.372~383 (2005)
- K. Wu, "Analyses of multi-level and multi-component compressed bitmap indexes", ACM Trans. Database Syst, 35(1) (2010)
- Jong P. Yoon, "Presto Authorization: A Bitmap Indexing Scheme for High-Speed Access Control to XML Documents", IEEE Trans. Knowl. Data Eng, 18(7), pp.971~987 (2006)
- Z. Zhang, "Bed-tree: an all-purpose index struc-ture for string similarity search based on edit distance", Proc.of SIGMOND Conf, pp.915~926 (2010)
- C. Zhu, "Efficient Processing of Monotonic Linear Progressive Queries via Dynamic Materialized Views", Proc.of CASCON Conf, pp.224~237 (2010)
- C. Zhu, "A Materialized-View Based Technique to Optimize Pro-gressive Queries via Dependency Analysis", Proc.of CASCON Conf, pp.60~73 (2011)
- C. Zhu, "Optimization of Monotonic Linear Progressive Queries Based on Dynamic Materialized Views", The Computer Journal (2013)
- C. Zhu, "A Dynamic Materialized View Index for Efficiently Discovering Usable Views for Progressive Queries", Proc.of CASCON Conf, pp.42~56 (2012)
- Q. Zhu, "The Collective index: A Technique for Efficient Processing of Progressive Queries", The Computer Journal, 51(6), pp.662~676 (2008)