Hostname: page-component-669899f699-8p65j Total loading time: 0 Render date: 2025-05-06T12:57:33.146Z Has data issue: false hasContentIssue false
  • English
  • Français

Context-preserving XQuery fusion

Published online by Cambridge University Press:  10 November 2014

H. KATO ,
S. HIDAKA ,
Z. HU ,
K. NAKANO  and
Y. ISHIHARA
H. KATO
Affiliation:
National Institute of Informatics, Japan Email: [email protected]
S. HIDAKA
Affiliation:
National Institute of Informatics, Japan Email: [email protected]
Z. HU
Affiliation:
National Institute of Informatics, Japan Email: [email protected]
K. NAKANO
Affiliation:
The University of Electro-Communications, Japan
Y. ISHIHARA
Affiliation:
Osaka University, Japan
Get access Rights & Permissions [Opens in a new window]

Abstract

This paper solves the known problem of elimination of unnecessary internal element construction as well as variable elimination in XML processing with (a subset of) XQuery without ignoring the issues of document order. The semantics of XQuery is context sensitive and requires preservation of document order. In this paper, we propose, as far as we are aware, the first XQuery fusion that can deal with both the document order and the context of XQuery expressions. More specifically, we carefully design a context representation of XQuery expressions based on the Dewey order encoding, develop a context-preserving XQuery fusion for ordered trees by static emulation of the XML store, and prove that our fusion is correct. Our XQuery fusion has been implemented, and all the examples in this paper have passed through the system.

Type
Paper
Information
Mathematical Structures in Computer Science , Volume 25 , Issue 4: APLAS 2010 , May 2015 , pp. 916 - 941
Copyright
Copyright © Cambridge University Press 2014 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

Article purchase

Temporarily unavailable

References

Amano, S., Libkin, L. and Murlak, F. (2009) XML schema mappings. In: Proceedings of the 28th ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems (PODS), ACM 33–42. http://doi.acm.org/10.1145/1559795.1559801.Google Scholar
Brundage, M. (2004) XQuery: The XML Query Language, Addison-Wesley.Google Scholar
Chin, W. (1992) Safe fusion of functional expressions. In: Proceedings of the Conference on Lisp and Functional Programming, San Francisco, California. ACM Press 11–20.Google Scholar
Daniels, S., Graefe, G., Keller, T., Maier, D., Schmidt, D. and Vance, B. (1991) Query optimization in revelation, an overview. Data Engineering 14 (2)58–62.Google Scholar
Deutsch, A., Papakonstantinou, Y. and Xu, Y. (2004) The NEXT framework for logical XQuery opimization. In: Proceedings of the 30th International Conference on Very Large Data Bases (VLDB), Morgan Kaufmann. 168–179. http://www.vldb.org/conf/2004/RS4P5.PDF.Google Scholar
Fegaras, L. (2010) Propagating updates through XML views using lineage tracing. In: Proceedings of the 26th International Conference on Data Engineering (ICDE), IEEE Computer Society 309–320.Google Scholar
Fegaras, L. and Maier, D. (2000) Optimizing object queries using an effective calculus. ACM Transactions on Database Systems (TODS) 25 (4)457–516.Google Scholar
Fernández, M., Hidders, J., Michiels, P., Siméon, J. and Vercammen, R. (2005) Optimizing sorting and duplicate elimination in XQuery path expressions. In: Proceedings of the 16th International Conference on Database and Expert Systems Applications (DEXA), Springer 554–563. http://dx.doi.org/10.1007/11546924_54.CrossRefGoogle Scholar
Gill, A., Launchbury, J. and Jones, S. L. P. (1993) A short cut to deforestation. In: Proceedings of the 6th Conference on Functional Programming Languages and Computer Architecture (FPCA), ACM Press 223–232.Google Scholar
Gottlob, G., Koch, C. and Pichler, R. (2005) Efficient algorithms for processing XPath queries. ACM Transactions on Database Systems (TODS) 30 (2)444–491.Google Scholar
Grust, T., Mayr, M. and Rittinger, J. (2010) Let SQL drive the XQuery workhorse (XQuery join graph isolation). In: Proceedings of the 13th International Conference on Extending Database Technology (EDBT), ACM Press 147–158. http://doi.acm.org/10.1145/1739041.1739062.CrossRefGoogle Scholar
Grust, T., Sakr, S. and Teubner, J. (2004) XQuery on SQL hosts. In: Proceedings of the 30th International Conference on Very Large Data Bases (VLDB), Morgan Kaufmann 252–263. http://www.vldb.org/conf/2004/RS7P1.PDF.Google Scholar
Gueni, B., Abdessalem, T., Cautis, B. and Waller, E. (2008). Pruning nested XQuery queries. In: Proceedings of the 17th ACM Conference on Information and Knowledge Management (CIKM), ACM 541–550. http://doi.acm.org/10.1145/1458082.1458154.Google Scholar
Hidders, J., Paredaens, J., Vercammen, R. and Demeyer, S. (2004). A light but formal introduction to XQuery. In: Proceedings of the Second International XML Database Symposium (XSym). Springer Lecture Notes in Computer Science 3186 5–20. http://dx.doi.org/10.1007/978-3-540-30081-6_2.Google Scholar
Koch, C. (2005) On the role of composition in XQuery. In: Proceedings of the 8th International Workshop on the Web and Databases (WebDB) 37–42.Google Scholar
Lu, J., Ling, T. W., Chan, C.-Y. and Chen, T. (2005) From region encoding to extended Dewey: On efficient processing of XML twig pattern matching. In: Proceedings of the 31st International Conference on Very Large Data Bases (VLDB), ACM 193–204. http://www.vldb2005.org/program/paper/tue/p193-lu.pdf.Google Scholar
Michiels, P., Manolescu, I. and Miachon, C. (2008) Toward microbenchmarking XQuery. Information Systems 33 (2)182–202. http://dx.doi.org/10.1016/j.is.2007.05.003.Google Scholar
Ohori, A. (1990) Representing object identity in a pure functional language. In: Proceedings of the 3rd International Conference on Database Theory (ICDT). Springer-Verlag Lecture Notes in Computer Science 470 41–55. http://dx.doi.org/10.1007/3-540-53507-1_69.Google Scholar
Ohori, A. and Sasano, I. (2007) Lightweight fusion by fixed point promotion. In: Proceedings of the 34th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL) 143–154. http://doi.acm.org/10.1145/1190216.1190241.Google Scholar
Page, W. L., Hidders, J., Michiels, P., Paredaens, J. and Vercammen, R. (2005) On the expressive power of node construction in XQuery. In: Proceedings of the 8th International Workshop on the Web and Databases (WebDB) 85–90.Google Scholar
Parys, P. (2009) XPath evaluation in linear time with polynomial combined complexity. In: Proceedings of the 28th ACM SIGMOD-SIGACT-SIGART. Symposium on Principles of Database Systems (PODS), ACM 55–64. http://doi.acm.org/10.1145/1559795.1559805.Google Scholar
Tatarinov, I. and Halevy, A. (2004) Efficient query reformulation in peer data management systems. In: Proceedings of the 2004 ACM SIGMOD International Conference on Management of Data (SIGMOD) 539–550. http://doi.acm.org/10.1145/1007568.1007629.Google Scholar
Tatarinov, I., Viglas, S. D., Beyer, K., Shanmugasundaram, J., Shekita, E. and Zhang, C. (2002) Storing and querying ordered XML using a relational database system. In: Proceedings of the 2002 ACM SIGMOD International Conference on Management of Data (SIGMOD) 204–215. http://doi.acm.org/10.1145/564691.564715.CrossRefGoogle Scholar
Wadler, P. (1988) Deforestation: Transforming programs to eliminate trees. In: Proceedings of the 2nd European Symposium on Programming (ESOP). Springer Lecture Notes in Computer Science 300 344–358. http://dx.doi.org/10.1007/3-540-19027-9_23.Google Scholar
World Wide Web Consortium (2010a) XQuery1.0: An XML query language. http://www.w3.org/TR/xquery/. W3C Recommendation.Google Scholar
World Wide Web Consortium (2010b) XQuery1.0 and XPath2.0 formal semantics. http://www.w3.org/TR/xquery-semantics/. W3C Recommendation.Google Scholar
Xu, L., Ling, T. W., Wu, H. and Bao, Z. (2009) DDE: From Dewey to a fully dynamic XML labelling scheme. In: Proceedings of the ACM SIGMOD International Conference on Management of Data (SIGMOD) 719–730. http://doi.acm.org/10.1145/1559845.1559921.Google Scholar