Identifying query incompatibilities with evolving XML schemas

ABSTRACT

During the life cycle of an XML application, both schemas and queries may change from one version to another. Schema evolutions may affect query results and potentially the validity of produced data. Nowadays, a challenge is to assess and accommodate the impact of these changes in evolving XML applications. Such questions arise naturally in XML static analyzers. These analyzers often rely on decision procedures such as inclusion between XML schemas, query containment and satisfiability. However, existing decision procedures cannot be used directly in this context. The reason is that they are unable to distinguish information related to the evolution from information corresponding to bugs. This paper proposes a predicate language within a logical framework that can be used to make this distinction.

We present a system for monitoring the effect of schema evolutions on the set of admissible documents and on the results of queries. The system is very powerful in analyzing various scenarios where the result of a query may not be anymore what was expected. Specifically, the system is based on a set of predicates which allow a fine-grained analysis for a wide range of forward and backward compatibility issues. Moreover, the system can produce counterexamples and witness documents which are useful for debugging purposes. The current implementation has been tested with realistic use cases, where it allows identifying queries that must be reformulated in order to produce the expected results across successive schema versions.

REFERENCES

• 1: Michael Benedikt and Christoph Koch. XPath leashed. submitted, 2006.
• 2: Michael Benedikt, Wenfei Fan, and Floris Geerts. XPath satisfiability in the presence of DTDs. In PODS '05, pages 25--36. ACM Press, 2005. ISBN 1-59593-062-0. http://doi.acm.org/10.1145/1065167.1065172.
• 3: Véronique Benzaken, Giuseppe Castagna, and Alain Frisch. CDuce: An XML-centric general-purpose language. In ICFP '03: Proceedings of the Eighth ACM SIGPLAN International Conference on Functional Programming, pages 51--63, New York, NY, USA, 2003. ACM Press. ISBN 1-58113-756-7.
• 4: an, Saiprasad, and der Linden]beyer-sigmod05Kevin Beyer, Fatma Özcan, Sundar Saiprasad, and Bert Van der Linden. DB2/XML: designing for evolution. In SIGMOD '05, pages 948--952. ACM, 2005. ISBN 1-59593-060-4. http://doi.acm.org/10.1145/1066157.1066299.
• 5: Giuseppe Castagna and Kim Nguyen. Typed iterators for XML. In ICFP, pages 15--26, 2008.
• 6: James Clark and Steve DeRose. XML path language (XPath) version 1.0, W3C recommendation, November 1999. http://www.w3.org/TR/ 1999/REC-xpath-19991116.
• 7: Dario Colazzo, Giorgio Ghelli, Paolo Manghi, and Carlo Sartiani. Types for path correctness of XML queries. In ICFP '04: Proceedings of the ninth ACM SIGPLAN international conference on Functional programming, pages 126--137, New York, NY, USA, 2004. ACM Press. ISBN 1-58113-905-5.
• 8: Dario Colazzo, Giorgio Ghelli, Paolo Manghi, and Carlo Sartiani. Static analysis for path correctness of XML queries. J. Funct. Program., 16 (4-5): 621--661, 2006. ISSN 0956-7968.
• 9: Vladimir Gapeyev, François Garillot, and Benjamin C. Pierce. Statically typed document transformation: An Xtatic experience. In PLAN-X 2006: Proceedings of the International Workshop on Programming Language Technologies for XML, volume NS-05-6 of BRICS Notes Series, pages 2--13, Aarhus, Denmark, January 2006. BRICS.
• 10: Pierre Genevès. Logics for XML. PhD thesis, Institut National Polytechnique de Grenoble, December 2006. http://www.pierresoft.com/pierre.geneves/phd.htm.
• 11: Pierre Genevès and Nabil Layaïda. The XML reasoning solver project, February 2009. http://wam.inrialpes.fr/xml.
• 12: Pierre Genevès, Nabil Layaïda, and Alan Schmitt. Efficient static analysis of XML paths and types. In PLDI '07, pages 342--351. ACM Press, 2007. ISBN 978-1-59593-633-2. http://doi.acm.org/10.1145/1250734.1250773.
• 13: Pierre Genevès, Nabil Layaïda, and Alan Schmitt. Efficient static analysis of XML paths and types. Long version of Geneves Et. Al. 07, Research Report 6590, INRIA, July 2008. URL http://hal.inria.fr/inria-00305302/en/.
• 14: Haruo Hosoya and Benjamin C. Pierce. XDuce: A statically typed XML processing language. ACM Trans. Inter. Tech., 3 (2): 117--148, 2003. ISSN 1533-5399.
• 15: Haruo Hosoya, Jérôme Vouillon, and Benjamin C. Pierce. Regular expression types for XML. phACM TOPLAS, 27 (1): 46--90, 2005. ISSN 0164-0925. http://doi.acm.org/10.1145/1053468.1053470.
• 16: Anders Møller and Michael I. Schwartzbach. The design space of type checkers for XML transformation languages. In Proc. Tenth International Conference on Database Theory, ICDT '05, volume 3363 of LNCS, pages 17--36, London, UK, January 2005. Springer-Verlag.
• 17: Hyun J. Moon, Carlo A. Curino, Alin Deutsch, and Chien-Yi Hou. Managing and querying transaction-time databases under schema evolution. In VLDB '08, pages 882--895. VLDB Endowment, 2008.
• 18: Mirella M. Moro, Susan Malaika, and Lipyeow Lim. Preserving xml queries during schema evolution. In WWW '07, pages 1341--1342. ACM, 2007. ISBN 978-1-59593-654-7. http://doi.acm.org/10.1145/1242572.1242841.
• 19: Makoto Murata, Dongwon Lee, Murali Mani, and Kohsuke Kawaguchi. Taxonomy of XML schema languages using formal language theory. ACM TOIT, 5 (4): 660--704, 2005. ISSN 1533-5399. http://doi.acm.org/10.1145/1111627.1111631.
• 20: Emmanuel Pietriga. MathML content2presentation transformation, May 2005. http://www.lri.fr/pietriga/mathmlc2p/mathmlc2p.html.
• 21: Kristoffer H. Rose. The XML world view. In DocEng '04: Proceedings of the 2004 ACM symposium on Document engineering, pages 34--34, New York, NY, USA, 2004. ACM. ISBN 1-58113-938-1. http://doi.acm.org/10.1145/1030397.1030403. URL http://www.research.ibm.com/XML/Rose--DocEng2004.pdf.
• 22: Eric Sedlar. Managing structure in bits & pieces: the killer use case for XML. In SIGMOD '05, pages 818--821. ACM, 2005. ISBN 1-59593-060-4. http://doi.acm.org/10.1145/1066157.1066256.
• 23: Philip Wadler. Two semantics for XPath. Internal Technical Note of the W3C XSL Working Group, http://homepages.inf.ed.ac.uk/wadler/papers/xpath-semantics/xpath-semantics.%pdf, January 2000.
• 24: Cong Yu and Lucian Popa. Semantic adaptation of schema mappings when schemas evolve. In VLDB '05, pages 1006--1017. VLDB Endowment, 2005. ISBN 1-59593-154-6.

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors

Additional Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.4 Software/Program Verification

General Terms:
Languages, Standardization, Verification

Keywords:
XML, analysis, compatibility, evolution, queries, schema