Evaluating Universal Quantification in XML
|
Queries posed to database systems often involve Universal Quantification. Such queries are typically expensive to evaluate. While they can be handled by basic access methods, for selection, grouping, etc., new access methods specifically tailored to evaluate universal quantification can greatly decrease the computational cost. In this paper, we study the efficient evaluation of universal quantification in an XML database. Specifically, we develop a small taxonomy of universal quantification types, and define a family of algorithms suitable for handling each. We experimentally demonstrate the performance benefits of the new family of algorithms.
[1] 1494 G. Graefe and R.L. Cole, “Fast Algorithms for Universal Quantification in Large Databases,” ACM Trans. Database Systems, vol. 20, no. 2, pp. 187-236, 1995.
[2] Univ. of Wisconsin, The Niagara System, http://www.cs.wisc. eduniagara/, 2006.
[3] Univ. of Michigan, The Timber System, http://www.eecs.umich. edu/dbtimber/, 2006.
[4] 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, and C. Yu, “Timber: A Native XML Database,” VLDBJ., vol. 11, no. 4, pp. 274-291, 2002.
[5] S. Al-Khalifa, H. Jagadish, N. Koudas, J. Patel, and D. Srivastava, “Structural Joins: A Primitive for Efficient XML Query Pattern Matching,” Proc. Int'l Conf. Data Eng., p. 141, 2002.
[6] G. Graefe, “Query Evaluation Techniques for Large Databases,” ACM Computing Surveys, vol. 25, no. 2, pp. 73-169, 1993.
[7] S. Chien, Z. Vagena, D. Zhang, V. Tsotras, and C. Zaniolo, “Efficient Structural Joins on Indexed XML Documents,” Proc. Int'l Conf. Very Large Data Bases, vol. 2, pp. 263-274, 2002.
[8] Sigmod Record—XML Version, http://www.dia.uniroma3.it/Araneus/Sigmod/ Record/HomePageindex.xml, 2005.
[9] The XML Benchmark Project, http:/www.xml-benchmark.org, 2006.
[10] J.M. Smith and P.Y.-T. Chang, “Optimizing the Performance of a Relational Algebra Database Interface,” Comm. ACM, vol. 18, no. 10, pp. 568-579, 1975.
[11] J.V. Carlis, “HAS, a Relational Algebra Operator or Divide Is Not Enough to Conquer,” Proc. Int'l Conf. Data Eng., pp. 254-261, 1986.
[12] R. Rantzau, L. Shapiro, B. Mitschang, and Q. Wang, “Universal Quantification in Relational Databases: A Classification of Data and Algorithms,” Proc. Int'l Conf. Extending Database Technology, pp. 445-463, 2002.
[13] K.-Y. Whang, A. Malhotra, G.H. Sockut, and L.M. Burns, “Supporting Universal Quantification in a Two-Dimensional Database Query Language,” Proc. Int'l Conf. Data Eng., pp. 68-75, 1990.
[14] P.-Y. Hsu and J. Douglas Stott Parker, “Improving SQL with Generalized Quantifiers” Proc. Int'l Conf. Data Eng., pp. 298-305, 1995.
[15] J. Claussen, A. Kemper, G. Moerkotte, and K. Peithner, “Optimizing Queries with Universal Quantification in Object-Oriented and Object-Relational Databases,” Proc. Int'l Conf. Very Large Data Bases, pp. 286-295, 1997.
[16] F. Bry, “Logical Rewritings for Improving the Evaluation of Quantified Queries,” Proc. Symp. Math. Fundamentals of Database Systems, pp. 100-116, 1989.
Index Terms:
Access methods, XML/XSL/RDF, Query processing
Citation:
Shurug Al-Khalifa, Bin Liu, H. V. Jagadish, "Evaluating Universal Quantification in XML," IEEE Transactions on Knowledge and Data Engineering, vol. 19, no. 11, pp. 1494-1507, July 2007, doi:10.1109/TKDE.2007.190643
PURCHASE ARTICLE: $19
IEEE Xplore Subscribers
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb