On the integration of structure indexes and inverted lists

ABSTRACT

Several methods have been proposed to evaluate queries over a native XML DBMS, where the queries specify both path and keyword constraints. These broadly consist of graph traversal approaches, optimized with auxiliary structures known as structure indexes; and approaches based on information-retrieval style inverted lists. We propose a strategy that combines the two forms of auxiliary indexes, and a query evaluation algorithm for branching path expressions based on this strategy. Our technique is general and applicable for a wide range of choices of structure indexes and inverted list join algorithms. Our experiments over the Niagara XML DBMS show the benefit of integrating the two forms of indexes. We also consider algorithmic issues in evaluating path expression queries when the notion of relevance ranking is incorporated. By integrating the above techniques with the Threshold Algorithm proposed by Fagin et al., we obtain instance optimal algorithms to push down top k computation.

REFERENCES

• 1: DBXplorer: A System for Keyword-Based Search over Relational Databases, Proceedings of the 18th International Conference on Data Engineering, p.5, February 26-March 01, 2002
• 2: Shurug Al-Khalifa , Cong Yu , H. V. Jagadish, Querying structured text in an XML database, Proceedings of the 2003 ACM SIGMOD international conference on Management of data, June 09-12, 2003, San Diego, California [doi>10.1145/872757.872761]
• 3: Sihem Amer-Yahia , SungRan Cho , Divesh Srivastava, Tree Pattern Relaxation, Proceedings of the 8th International Conference on Extending Database Technology: Advances in Database Technology, p.496-513, March 25-27, 2002
• 4: A. Arion et al. XQueC: Pushing queries to compressed XML data. In VLDB, 2003.
• 5: G. Bhalotia et al. Keyword searching and browsing in databases using BANKS. In ICDE, 2002.
• 6: N. Bruno, L. Gravano, and A. Marian. Evaluating top-k queries over web-accessible databases. In ICDE, 2002.
• 7: Nicolas Bruno , Nick Koudas , Divesh Srivastava, Holistic twig joins: optimal XML pattern matching, Proceedings of the 2002 ACM SIGMOD international conference on Management of data, June 03-06, 2002, Madison, Wisconsin [doi>10.1145/564691.564727]
• 8: P. Buneman, M. Grohe, and C. Koch. Path queries on compressed XML. In VLDB, 2003.
• 9: D. Chamberlin, D. Florescu, J. Robie, J. Siméon, and M. Stefanescu. XQuery: A query language for XML. World Wide Web Consortium, http://www.w3.org/TR/xquery, Feb 2000.
• 10: S. Chien, Z. Vagena, D. Zhang, V. J. Tsotras, and C. Zaniolo. Efficient structural joins on indexed XML documents. In VLDB, 2002.
• 11: Brian Cooper , Neal Sample , Michael J. Franklin , Gisli R. Hjaltason , Moshe Shadmon, A Fast Index for Semistructured Data, Proceedings of the 27th International Conference on Very Large Data Bases, p.341-350, September 11-14, 2001
• 12: Shaul Dar , Gadi Entin , Shai Geva , Eran Palmon, DTL's DataSpot: Database Exploration Using Plain Language, Proceedings of the 24rd International Conference on Very Large Data Bases, p.645-649, August 24-27, 1998
• 13: Ronald Fagin , Amnon Lotem , Moni Naor, Optimal aggregation algorithms for middleware, Proceedings of the twentieth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.102-113, May 2001, Santa Barbara, California, United States [doi>10.1145/375551.375567]
• 14: Norbert Fuhr , Kai Großjohann, XIRQL: a query language for information retrieval in XML documents, Proceedings of the 24th annual international ACM SIGIR conference on Research and development in information retrieval, p.172-180, September 2001, New Orleans, Louisiana, United States [doi>10.1145/383952.383985]
• 15: N. Fuhr, M. Lalmas, and S. Malik. INEX: initiative for evaluation of XML retrieval. http://inex.is.informatik. uniduisburg.de:2003
• 16: Roy Goldman , Narayanan Shivakumar , Suresh Venkatasubramanian , Hector Garcia-Molina, Proximity Search in Databases, Proceedings of the 24rd International Conference on Very Large Data Bases, p.26-37, August 24-27, 1998
• 17: Roy Goldman , Jennifer Widom, DataGuides: Enabling Query Formulation and Optimization in Semistructured Databases, Proceedings of the 23rd International Conference on Very Large Data Bases, p.436-445, August 25-29, 1997
• 18: Lin Guo , Feng Shao , Chavdar Botev , Jayavel Shanmugasundaram, XRANK: ranked keyword search over XML documents, Proceedings of the 2003 ACM SIGMOD international conference on Management of data, June 09-12, 2003, San Diego, California [doi>10.1145/872757.872762]
• 19: A. Halverson et al. Mixed mode XML query processing. In VLDB, 2003.
• 20: Marti A. Hearst , Christian Plaunt, Subtopic structuring for full-length document access, Proceedings of the 16th annual international ACM SIGIR conference on Research and development in information retrieval, p.59-68, June 27-July 01, 1993, Pittsburgh, Pennsylvania, United States [doi>10.1145/160688.160695]
• 21: V. Hristidis, L. Gravano, and Y. Papakonstantinou. Efficient IR-style keyword search over relational databases. In VLDB, 2003.
• 22: H. V. Jagadish , S. Al-Khalifa , A. Chapman , L. V. S. Lakshmanan , A. Nierman , S. Paparizos , J. M. Patel , D. Srivastava , N. Wiwatwattana , Y. Wu , C. Yu, TIMBER: A native XML database, The VLDB Journal — The International Journal on Very Large Data Bases, v.11 n.4, p.274-291, December 2002 [doi>10.1007/s00778-002-0081-x]
• 23: H. Jiang, H. Lu, W. Wang, and B. C. Ooi. XR-Tree: Indexing XML Data for Efficient Structural Joins. In ICDE, 2003.
• 24: H. Jiang, H. Lu, W. Wang, and J. X. Yu. XParent: An Efficient RDBMS-Based XML Database System. In ICDE, 2002.
• 25: Shriraghav Kaushik , Jeffrey F. Naughton, Graph summarization for indexing paths in graph-structured data, 2003
• 26: Raghav Kaushik , Philip Bohannon , Jeffrey F Naughton , Henry F Korth, Covering indexes for branching path queries, Proceedings of the 2002 ACM SIGMOD international conference on Management of data, June 03-06, 2002, Madison, Wisconsin [doi>10.1145/564691.564707]
• 27: Quanzhong Li , Bongki Moon, Indexing and Querying XML Data for Regular Path Expressions, Proceedings of the 27th International Conference on Very Large Data Bases, p.361-370, September 11-14, 2001
• 28: R. Luk et al. A survey of search engines for XML documents. In SIGIR Workshop on XML and IR, 2000.
• 29: Y. Mass, M. Mandelbrod, E. Amitay, Y. Maarek, and A. Soffer. JuruXML: An XML retrieval system. In INEX Workshop, 2002.
• 30: Jason McHugh , Jennifer Widom, Query Optimization for XML, Proceedings of the 25th International Conference on Very Large Data Bases, p.315-326, September 07-10, 1999
• 31: Tova Milo , Dan Suciu, Index Structures for Path Expressions, Proceeding of the 7th International Conference on Database Theory, p.277-295, January 10-12, 1999
• 32: Sung Hyon Myaeng , Don-Hyun Jang , Mun-Seok Kim , Zong-Cheol Zhoo, A flexible model for retrieval of SGML documents, Proceedings of the 21st annual international ACM SIGIR conference on Research and development in information retrieval, p.138-145, August 24-28, 1998, Melbourne, Australia [doi>10.1145/290941.290980]
• 33: XML astronomy archive at NASA. http://xml.gsfc.nasa.gov/archive.
• 34: J. Naughton, D. DeWitt, D. Maier, et al. The Niagara Internet Query System. In IEEE Data Engineering Bulletin, 2001.
• 35: Gonzalo Navarro , Ricardo Baeza-Yates, Proximal nodes: a model to query document databases by content and structure, ACM Transactions on Information Systems (TOIS), v.15 n.4, p.400-435, Oct. 1997 [doi>10.1145/263479.263482]
• 36: T. Schlieder and H. Meuss. Result ranking for structured queries against XML documents. In DELOS Workshop on Information Seeking, Searching and Querying in Digital Libraries, 2000.
• 37: D. Srivastava, S. Al-Khalifa, H. Jagadish, N. Koudas, J. Patel, and Y. Wu. Structural joins: A primitive for efficient XML query pattern matching. In ICDE, 2002.
• 38: Anja Theobald , Gerhard Weikum, The Index-Based XXL Search Engine for Querying XML Data with Relevance Ranking, Proceedings of the 8th International Conference on Extending Database Technology: Advances in Database Technology, p.477-495, March 25-27, 2002
• 39: Personal communication with Haixun Wang.
• 40: Haixun Wang , Sanghyun Park , Wei Fan , Philip S. Yu, ViST: a dynamic index method for querying XML data by tree structures, Proceedings of the 2003 ACM SIGMOD international conference on Management of data, June 09-12, 2003, San Diego, California [doi>10.1145/872757.872774]
• 41: W. Wang, H. Jiang, H. Lu, and J. X. Yu. PBiTree Coding and Efficient Processing of Containment Joins. In ICDE, 2003.
• 42: XMark: The XML benchmark project. http://monetdb.cwi.nl/xml/index.html.
• 43: XRel: a path-based approach to storage and retrieval of XML documents using relational databases, ACM Transactions on Internet Technology (TOIT), v.1 n.1, p.110-141, Aug. 2001 [doi>10.1145/383034.383038]