XPath on left and right sides of rules: toward compact XML tree rewriting through node patterns

ABSTRACT

XPath [3, 5] is a powerful and quite successful language able to perform complex node selection in trees through compact specifications. As such, it plays a growing role in many areas ranging from schema specifications, designation and transformation languages to XML query languages. Moreover, researchers have proposed elegant and tractable formal semantics [8, 9, 10, 14], fostering various works on mathematical properties and theoretical tools [10, 13, 12, 14].We propose here a novel way to consider XPath, not only for selecting nodes, but also for tree rewriting using rules. In the rule semantics we explore, XPath expressions (noted p,p') are used both on the left and on the right side (i.e. rules have the form p → p'). We believe that this proposal opens new perspectives toward building highly concise XML transformation languages on widely accepted basis.

REFERENCES

• 1: N. Dershowitz, J.-P. Jouanaud "Handbook of Theoretical Computer Science", Chapter on Rewriting, pp. 243--320 Elsevier, 1990.
• 2: H. Common, M. Dauchet, R. Gilleron, F. Jacquemard, D. Lugiez, S. Tison and M. Tommasi "Tree Automata Techniques and Applications", Technical Report, www.grappa.univ-lille3.fr/tata, October, 1999.
• 3: XML Path Language (XPath) 1.0, W3C recommendation, 16 November, 1999.
• 4: Document Object Model (DOM) 1.0, W3C recommendation, October, 1998.
• 5: XML Path Language (XPath) 2.0, W3C working draft, 15 November, 2002.
• 6: Mathematical Markup Language (MathML) 2.0, W3C Recommendation, 21 February, 2001.
• 7: Michael Kohlhase, New MathML tutorial, W3C working group, www.w3.org/Math/Documents/mathml-tutorial.pdf, 11 March, 2003.
• 8: Phil Wadler, "A formal semantics of patterns in XSLT", Markup Technologies, 1999.
• 9: Phil Wadler, "Two semantics for XPath", www.cs.bell-labs.com/who/wadler/topics/xml.html, 1999.
• 10: Dan Olteanu and Holger Meuss and Tim Furche and François Bry, "Symmetry in XPath", technical report, October 2001, Computer Science Institute, Munich, Germany.
• 11: Alin Deutsch and Val Tannen, "Containment of Regular Path Expressions under Integrity Constraints", Knowledge Representation Meets Databases, 2001.
• 12: Frank Neven , Thomas Schwentick, XPath Containment in the Presence of Disjunction, DTDs, and Variables, Proceedings of the 9th International Conference on Database Theory, p.315-329, January 08-10, 2003
• 13: Gerome Miklau , Dan Suciu, Containment and equivalence for an XPath fragment, Proceedings of the twenty-first ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 03-05, 2002, Madison, Wisconsin [doi>10.1145/543613.543623]
• 14: Jean-Yves Vion-Dury and Nabil Layaïda, "Containment of XPath Expressions: an Inference and Rewriting based approach ", Extreme Markup Languages, Montréal August, 2003. http://wam.inrialpes.fr/publications/2003/xtrem2003/xtrem2003.pdf
• 15: Emmanuel Piétriga, MathMLc2p, XSLT based translation of content MathML into presentation MathML, April, 2000. http://opera.inrialpes.fr/people/Emmanuel.Pietriga/mathml2cp.html
• 16: Wolfgang May "XPath-Logic and PathLog: A Logic-Based Approach for Declarative XML Data Manipulation", Technical Report No. 149, Institut für Informatik, Freiburg, Germany Feb, 2001.
• 17: WAM "Web Adaptation and Multimedia", Research project from INRIA Rhône-Alpes, http://wam.inrialpes.fr

INDEX TERMS

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

General Terms:
Design, Languages, Theory