FLUX: functional updates for XML

ABSTRACT

XML database query languages have been studied extensively, but XML database updates have received relatively little attention, and pose many challenges to language design. We are developing an XML update language called FLUX, which stands for FunctionaL Updates for XML, drawing upon ideas from functional programming languages. In prior work, we have introduced a core language for FLUX with a clear operational semantics and a sound, decidable static type system based on regular expression types.

Our initial proposal had several limitations. First, it lacked support for recursive types or update procedures. Second, although a high-level source language can easily be translated to the core language, it is difficult to propagate meaningful type errors from the core language back to the source. Third, certain updates are wellformed yet contain path errors, or "dead" subexpressions which never do any useful work. It would be useful to detect path errors, since they often represent errors or optimization opportunities.

In this paper, we address all three limitations. Specifically, we present an improved, sound type system that handles recursion. We also formalize a source update language and give a translation to the core language that preserves and reflects typability. We also develop a path-error analysis (a form of dead-code analysis) for updates.

REFERENCES

• 1: Andrey Balmin , Yannis Papakonstantinou , Victor Vianu, Incremental validation of XML documents, ACM Transactions on Database Systems (TODS), v.29 n.4, December 2004 [doi>10.1145/1042046.1042050]
• 2: Denilson Barbosa , Alberto O. Mendelzon , Leonid Libkin , Laurent Mignet , Marcelo Arenas, Efficient Incremental Validation of XML Documents, Proceedings of the 20th International Conference on Data Engineering, p.671, March 30-April 02, 2004
• 3: Michael Benedikt, Angela Bonifati, Sergio Flesca, and Avinash Vyas. Verification of tree updates for optimization. In Kousha Etessami and Sriram K. Rajamani, editors, CAV, volume 3576 of Lecture Notes in Computer Science, pages 379--393. Springer, 2005a.
• 4: Michael Benedikt, Angela Bonifati, Sergio Flesca, and Avinash Vyas. Adding updates to XQuery: Semantics, optimization, and static analysis. In Daniela Florescu and Hamid Pirahesh, editors, XIME-P, 2005b.
• 5: Véronique Benzaken , Giuseppe Castagna , Alain Frisch, CDuce: an XML-centric general-purpose language, Proceedings of the eighth ACM SIGPLAN international conference on Functional programming, p.51-63, August 25-29, 2003, Uppsala, Sweden
• 6: Geert Jan Bex , Frank Neven , Jan Van den Bussche, DTDs versus XML schema: a practical study, Proceedings of the 7th International Workshop on the Web and Databases: colocated with ACM SIGMOD/PODS 2004, June 17-18, 2004, Paris, France [doi>10.1145/1017074.1017095]
• 7: Peter Buneman , Shamim Naqvi , Val Tannen , Limsoon Wong, Principles of programming with complex objects and collection types, Theoretical Computer Science, v.149 n.1, p.3-48, Sept. 18, 1995
• 8: Cristiano Calcagno , Philippa Gardner , Uri Zarfaty, Context logic and tree update, Proceedings of the 32nd ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.271-282, January 12-14, 2005, Long Beach, California, USA
• 9: Don Chamberlin and Jonathan Robie. XQuery update facility requirements. W3C Working Draft, June 2005. http://www.w3.org/TR/xquery-update-requirements/.
• 10: Don Chamberlin, Mike Carey, Daniela Florescu, Donald Kossmann, and Jonathan Robie. XQueryP: Programming with XQuery. In XIME-P, 2006.
• 11: Don Chamberlin, Daniela Florescu, Jim Melton, Jonathan Robie, and Jérôme Siméon. XQuery update facility. W3C Candidate Recommendation, March 2008. http://www.w3c.org/TR/xquery-update-10/.
• 12: James Cheney. Lux: A lightweight, statically typed XML update language. In PLAN-X, pages 25--36, 2007.
• 13: James Cheney. Regular expression subtyping for XML query and update languages. In Proceedings of the 17th European Symposium on Programming (ESOP 2008), number 4960 in LNCS, pages 32--46, 2008a.
• 14: James Cheney. Flux: Functional updates for XML. Technical Report 2008. http://www.w3c.org/TR/xquery-update-10/.
• 15: Byron Choi. What are real DTDs like? In WebDB, pages 43--48, 2002.
• 16: J. Clark. XSL transformations (XSLT). W3C Recommendation, November 1999. http://www.w3.org/TR/xslt.
• 17: Dario Colazzo , Giorgio Ghelli , Paolo Manghi , Carlo Sartiani, Static analysis for path correctness of XML queries, Journal of Functional Programming, v.16 n.4-5, p.621-661, July 2006 [doi>10.1017/S0956796806005983]
• 18: Denise Draper, Peter Fankhauser, Mary Fernández, Ashok Malhotra, Kristoffer Rose, Michael Rys, Jérôme Siméon, and ilip Wadler. XQuery 1.0 and XPath 2.0 formal semantics. W3C Recommendation, January 2007. http://www.w3.org/TR/xquery-semantics/.
• 19: Mary F. Fernandez , Jérôme Siméon , Philip Wadler, A Semi-monad for Semi-structured Data, Proceedings of the 8th International Conference on Database Theory, p.263-300, January 04-06, 2001
• 20: Alain Frisch, OCaml + XDuce, Proceedings of the eleventh ACM SIGPLAN international conference on Functional programming, September 16-21, 2006, Portland, Oregon, USA
• 21: Vladimir Gapeyev, Franc¸ois Garillot, and Benjamin C. Pierce. Statically typed document transformation: An Xtatic experience. In Giuseppe Castagna and Mukund Raghavachari, editors, PLAN-X, pages 2--13. BRICS, 2006.
• 22: Philippa A. Gardner , Gareth D. Smith , Mark J. Wheelhouse , Uri D. Zarfaty, Local Hoare reasoning about DOM, 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.1376953]
• 23: G. Ghelli, K. Rose, and J. Sim´eon. Commutativity analysis in XML update languages. In Dan Suciu and Thomas Schwentick, editors, Proceedings of the 11th International Conference on Database Theory (ICDT 2007), pages 374--388, January 2007a.
• 24: Giorgio Ghelli, Christopher Re, and Jérôme Siméon. XQuery!: An XML query language with side effects. In EDBT Workshops, volume 4254 of Lecture Notes in Computer Science, pages 178--191. Springer, 2006.
• 25: Giorgio Ghelli, Nicola Onose, Kristoffer Rose, and Jérôme Siméon. A better semantics for XQuery with side-effects. In Marcelo Arenas and Michael I. Schwartzbach, editors, DBPL, volume 4797 of Lecture Notes in Computer Science, pages 81--96. Springer, 2007b.
• 26: Haruo Hosoya , Benjamin C. Pierce, XDuce: A statically typed XML processing language, ACM Transactions on Internet Technology (TOIT), v.3 n.2, p.117-148, May 2003 [doi>10.1145/767193.767195]
• 27: Haruo Hosoya , Jérôme Vouillon , Benjamin C. Pierce, Regular expression types for XML, ACM Transactions on Programming Languages and Systems (TOPLAS), v.27 n.1, p.46-90, January 2005 [doi>10.1145/1053468.1053470]
• 28: John Hughes, Generalising monads to arrows, Science of Computer Programming, v.37 n.1-3, p.67-111, May 2000 [doi>10.1016/S0167-6423(99)00023-4]
• 29: Andreas Laux and Lars Martin. XUpdate - XML update language. http://xmldb-org.sourceforge.net/xupdate/-xupdate-wd.html, September 2000. Work in progress.
• 30: Hartmut Liefke , Susan B. Davidson, Specifying Updates in Biomedical Databases, Proceedings of the 11th International Conference on Scientific on Scientific and Statistical Database Management, p.44, July 28-30, 1999 [doi>10.1109/SSDM.1999.787620]
• 31: Anders Møller and Michael I. Schwartzbach. The design space of type checkers for XML transformation languages. In Proceedings of the 10th International Conference on Database Theory (ICDT 2005), pages 17--36, 2005.
• 32: Gargi Sur, Joachim Hammer, and Jérôme Siméon. UpdateX - an XQuery-based language for processing updates in XML. In PLAN-X, 2004.
• 33: Igor Tatarinov , Zachary G. Ives , Alon Y. Halevy , Daniel S. Weld, Updating XML, Proceedings of the 2001 ACM SIGMOD international conference on Management of data, p.413-424, May 21-24, 2001, Santa Barbara, California, United States
• 34: Guoren Wang, Mengchi Liu, and Li Lu. Extending XML-RL with update. In IDEAS, pages 66--75. IEEE Computer Society, 2003.

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.1 Formal Definitions and Theory

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.3 Languages
          Subjects: Data manipulation languages (DML)

General Terms:
Languages

Keywords:
XML, static analysis, type systems, update languages