Sub-document queries over XML with XSQirrel

ABSTRACT

This paper describes XSQirrel, a new XML query language that transforms a document into a sub-document, i.e. a tree where the root-to-leaf paths are a subset of the root-to-leaf paths from the original document.We show that this type of queries is extremely useful for various applications (e.g. web services) and that the currently existing query languages are poorly equipped to express, reason and evaluate such queries. In particular, we emphasize the need to be able to compose such queries. We present the XSQirrel language with its syntax, semantics and two language specific operators, union and composition.For the evaluation of the language, we leverage well established query technologies by translating XSQirrel expressions into XPath programs, XQuery queries or XSLT stylesheets.We provide some experimental results that compare our various evaluation strategies. We also show the runtime benefits of query composition over sequential evaluation.

REFERENCES

• 1: The Third Generation Partnership Project (3GPP). http://www.3gpp.org.
• 2: S. Abiteboul, B. Alexe, O. Benjelloun, B. Cautis, I. Fundulaki, T. Milo, and A. Sahuguet. An Electronic Patient Record "on Steroids": Distributed, Peer-to-Peer, Secure and Privacy-conscious. In VLDB, 2004. (demo track).
• 3: Serge Abiteboul , Angela Bonifati , Grégory Cobéna , Ioana Manolescu , Tova Milo, Dynamic XML documents with distribution and replication, Proceedings of the 2003 ACM SIGMOD international conference on Management of data, June 09-12, 2003, San Diego, California [doi>10.1145/872757.872821]
• 4: C. Barton, P. Charles, D. Goyal, M. Raghavachari, M. Fontoura, and V. Josifovski. Streaming XPath Processing with Forward and Backward Axes. In ICDE, 2004.
• 5: M. Benedikt and I. Fundulaki. Specification and Composition of Subtree Queries. Technical Report, Bell Labs. http://db.bell-labs.com.
• 6: Elisa Bertino , Silvana Castano , Elena Ferrari, Securing XML documents: the author-X project demonstration, Proceedings of the 2001 ACM SIGMOD international conference on Management of data, p.605, May 21-24, 2001, Santa Barbara, California, United States
• 7: Francois Bry , Fatih Coskun , Serap Durmaz , Tim Furche , Dan Olteanu , Markus Spannagel, The XML Stream Query Processor SPEX, Proceedings of the 21st International Conference on Data Engineering (ICDE'05), p.1120-1121, April 05-08, 2005 [doi>10.1109/ICDE.2005.141]
• 8: Peter Buneman , Susan Davidson , Wenfei Fan , Carmem Hara , Wang-Chiew Tan, Keys for XML, Proceedings of the 10th international conference on World Wide Web, p.201-210, May 01-05, 2001, Hong Kong, Hong Kong [doi>10.1145/371920.371984]
• 9: D. Chamberlin, D. Florescu, J. Robie, J. Simeon, and L. Stefanescu. XQuery: A Query Language for XML. http://www.w3.org/TR/xquery, February 2001.
• 10: J. Clark and S. D. (eds.). XML Path Language (XPath) Version 1.0, 1999. http://www.w3c.org/TR/xpath.
• 11: Wenfei Fan , Chee-Yong Chan , Minos Garofalakis, Secure XML querying with security views, Proceedings of the 2004 ACM SIGMOD international conference on Management of data, June 13-18, 2004, Paris, France [doi>10.1145/1007568.1007634]
• 12: Mary Fernández , Yana Kadiyska , Dan Suciu , Atsuyuki Morishima , Wang-Chiew Tan, SilkRoute: A framework for publishing relational data in XML, ACM Transactions on Database Systems (TODS), v.27 n.4, p.438-493, December 2002 [doi>10.1145/582410.582413]
• 13: Irini Fundulaki , Arnaud Sahuguet, "Share your data, keep your secrets.", Proceedings of the 2004 ACM SIGMOD international conference on Management of data, June 13-18, 2004, Paris, France [doi>10.1145/1007568.1007712]
• 14: Liberty Alliance Project. http://www.projectliberty.org.
• 15: Liberty Alliance ID-WSF Data Services Template Specification, Version 1.0. http://www.projectliberty.org/specs/liberty-idwsf-dst-v1.0.pdf, 2002.
• 16: I. Manolescu and Y. Papakonstantinou, editors. Proceedings of the First International Workshop on XQuery Implementation, Experience and Perspectives <XIME-P/>, June 2004, Paris, France, 2004.
• 17: A. Marian and J. Simeon. Projecting XML Documents. In VLDB, 2003.
• 18: M. Petropoulos, A. Deutch, and Y. Papakonstantinou. Query Set Specification Language (QSSL). In Informal Proc. WEBDB, 2003.
• 19: Raghu Ramakrishnan , Johannes Gehrke, Database Management Systems, McGraw-Hill Science/Engineering/Math, 2002
• 20: J. Rosenberg. The Extensible Markup Language (XML) Configuration Access Protocol (XCAP). IETF draft, Feb 2004. http://www.jdrosen.net/papers/draft-ietf-simple-xcap-02.txt.
• 21: A. Sahuguet, B. Alexe, P.-Y. Laligand, A. Shikfa, and I. Fundulaki. User Profile Management in Converged Networks (Episode II): Share your data, Keep your secrets. In CIDR, Asilomar, CA, USA, January 2005. Online Proceedings.
• 22: A. Sahuguet, R. Hull, D. Lieuwen, and M. Xiong. Enter Once, Share Everywhere: User Profile Management in Converged Networks. In CIDR, Asilomar, CA, USA, January 2003. Online Proceedings.
• 23: Albrecht Schmidt , Florian Waas , Martin Kersten , Daniela Florescu , Michael J. Carey , Ioana Manolescu , Ralph Busse, Why and how to benchmark XML databases, ACM SIGMOD Record, v.30 n.3, September 2001 [doi>10.1145/603867.603872]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.3 Languages
          Subjects: Query languages

General Terms:
Algorithms, Languages, Performance

Keywords:
XML, XSQirrel, sub-document