Query ranking in probabilistic XML data

ABSTRACT

Twig queries have been extensively studied as a major fragment of XPATH queries to query XML data. In this paper, we study PXML-RANK query, (Q, k), which is to rank top-k probabilities of the answers of a twig query Q in probabilistic XML (PXML) data. A new research issue is how to compute top-k probabilities of answers of a twig query Q in PXML in the presence of containment (ancestor/descendant) relationships. In the presence of the ancestor/descendant relationships, the existing dynamic programming approaches to rank top-k probabilities over a set of tuples cannot be directly applied, because any node/edge in PXML may have impacts on the top-k probabilities of answers. We propose new algorithms to compute PXML-RANK queries efficiently and give conditions under which a PXML-RANK query can be processed efficiently without enumeration of all the possible worlds. We conduct extensive performance studies using both real and large benchmark datasets, and confirm the efficiency of our algorithms.

REFERENCES

• 1: S. Abiteboul and P. Senellart. Querying and updating probabilistic information in XML. In Proc. of EDBT'06, pages 1059--1068, 2006.
• 2: Sihem Amer-Yahia , Nick Koudas , Amélie Marian , Divesh Srivastava , David Toman, Structure and content scoring for XML, Proceedings of the 31st international conference on Very large data bases, August 30-September 02, 2005, Trondheim, Norway
• 3: Arvind Hulgeri , Charuta Nakhe, Keyword Searching and Browsing in Databases using BANKS, Proceedings of the 18th International Conference on Data Engineering, p.431, February 26-March 01, 2002
• 4: 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]
• 5: Sara Cohen , Benny Kimelfeld , Yehoshua Sagiv, Incorporating constraints in probabilistic XML, Proceedings of the twenty-seventh ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 09-12, 2008, Vancouver, Canada [doi>10.1145/1376916.1376933]
• 6: Sara Cohen , Jonathan Mamou , Yaron Kanza , Yehoshua Sagiv, XSEarch: a semantic search engine for XML, Proceedings of the 29th international conference on Very large data bases, p.45-56, September 09-12, 2003, Berlin, Germany
• 7: 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]
• 8: 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]
• 9: M. Hua, J. Pei, W. Zhang, and X. Lin. Efficiently answering probabilistic threshold top-k queries on uncertain data. In Proc. of ICDE'08, pages 1403--1405, 2008.
• 10: Ming Hua , Jian Pei , Wenjie Zhang , Xuemin Lin, Ranking queries on uncertain data: a probabilistic threshold approach, Proceedings of the 2008 ACM SIGMOD international conference on Management of data, June 09-12, 2008, Vancouver, Canada [doi>10.1145/1376616.1376685]
• 11: Edward Hung , Lise Getoor , V. S. Subrahmanian, Probabilistic Interval XML, Proceedings of the 9th International Conference on Database Theory, p.361-377, January 08-10, 2003
• 12: E. Hung, L. Getoor, and V. S. Subrahmanian. PXML: A probabilistic semistructured data model and algebra. In Proc. of ICDE'03, 2003.
• 13: Cheqing Jin , Ke Yi , Lei Chen , Jeffrey Xu Yu , Xuemin Lin, Sliding-window top-k queries on uncertain streams, Proceedings of the VLDB Endowment, v.1 n.1, August 2008 [doi>10.1145/1453856.1453892]
• 14: Benny Kimelfeld , Yuri Kosharovsky , Yehoshua Sagiv, Query efficiency in probabilistic XML models, Proceedings of the 2008 ACM SIGMOD international conference on Management of data, June 09-12, 2008, Vancouver, Canada [doi>10.1145/1376616.1376687]
• 15: B. Kimelfeld and Y. Sagiv. Twig patterns: From XML trees to graphs. In Proc. of WebDB'06, 2006.
• 16: Andrew Nierman , H. V. Jagadish, ProTDB: probabilistic data in XML, Proceedings of the 28th international conference on Very Large Data Bases, p.646-657, August 20-23, 2002, Hong Kong, China
• 17: L. Qin, J. X. Yu, and B. Ding. TwigList: Make twig pattern matching fast. In Proc. of DASFAA'07, pages 850--862, 2007.
• 18: C. Re, N. N. Dalvi, and D. Suciu. Efficient top-k query evaluation on probabilistic data. In Proc. of ICDE'07, pages 886--895, 2007.
• 19: Torsten Schlieder , Holger Meuss, Querying and ranking XML documents, Journal of the American Society for Information Science and Technology, v.53 n.6, p.489-503, May, 2002 [doi>10.1002/asi.10060]
• 20: Pierre Senellart , Serge Abiteboul, On the complexity of managing probabilistic XML data, Proceedings of the twenty-sixth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 11-13, 2007, Beijing, China [doi>10.1145/1265530.1265570]
• 21: M. A. Soliman, I. F. Ilyas, and K. C.-C. Chang. Top-k query processing in uncertain databases. In Proc. of ICDE'07, pages 896--905, 2007.
• 22: Maurice van Keulen , Ander de Keijzer , Wouter Alink, A Probabilistic XML Approach to Data Integration, Proceedings of the 21st International Conference on Data Engineering, p.459-470, April 05-08, 2005 [doi>10.1109/ICDE.2005.11]
• 23: K. Yi, F. Li, G. Kollios, and D. Srivastava. Efficient processing of top-k queries in uncertain databases. In Proc. of ICDE'08, 2008.
• 24: K. Yi, F. Li, G. Kollios, and D. Srivastava. Efficient processing of top-k queries in uncertain databases with x-relations. In Proc. of TKDE'08, 2008.
• 25: X. Zhang and J. Chomicki. On the semantics and evaluation of top-k queries in probabilistic databases. In Proc. of DBRank'08, pages 556--563, 2008.