Checking potential validity of XML documents

ABSTRACT

The process of creation of document-centric XML documents often starts with a prepared textual content, into which the editor introduces markup. In such situations, intermediate XML is almost never valid with respect to the DTD/Schema used for the encoding. At the same time, it is important to ensure that at each moment of time, the editor is working with an XML document that can enriched with further markup to become valid. In this paper we introduce the notion of potential validity of XML documents, which allows us to distinguish between XML documents that are invalid because the encoding is simply incomplete and XML documents that are invalid because some of the DTD rules guiding the structure of the encoding were violated during the markup process. We give a linear-time algorithm for checking potential validity for documents.

REFERENCES

• 1: Alfred V. Aho , Ravi Sethi , Jeffrey D. Ullman, Compilers: principles, techniques, and tools, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1986
• 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: B. Bouchou and M. H. F. Alves. Updates and Incremental Validation of XML Documents. In DBPL, 2003.
• 4: T. Bray, J. Paoli, C. M. Sperberg-McQueen, and E. Maler. Extensible Markup Language (XML) 1.0 (Second Edition). http://www.w3.org/TR/REC-xml, Oct 2000.
• 5: A. Brüggemann-Klein and D. Wood. On predictive parsing and extended context-free grammars, 2003.
• 6: J. Clark. Incremental XML Parsing and Validation in a Text Editor, December 2003. Presentation at XML 2003, Philadelphia.
• 7: Jay Earley, An efficient context-free parsing algorithm, Communications of the ACM, v.13 n.2, p.94-102, Feb 1970 [doi>10.1145/362007.362035]
• 8: Seymour Ginsburg, The Mathematical Theory of Context-Free Languages, McGraw-Hill, Inc., New York, NY, 1966
• 9: S. Heilbrunner. On the definition of ELR(k) and ELL(k) grammars. Acta Informatica, 11:169--176, 1979.
• 10: I. E. Iacob, A. Dekhtyar, and M. Dekhtyar. Checking Potential Validity of XML Documents. Technical Report TR 403-04, May 2004. http://www.cs.uky.edu/~dekhtyar/publications/TR403-04.pvalidity.ps.
• 11: Yannis Papakonstantinou , Victor Vianu, Incremental Validation of XML Documents, Proceedings of the 9th International Conference on Database Theory, p.47-63, January 08-10, 2003
• 12: Heung-Chul Shin , Kwang-Moo Choe, An improved LALR(k) parser generation for regular right part grammars, Information Processing Letters, v.47 n.3, p.123-129, Sept. 14, 1993 [doi>10.1016/0020-0190(93)90235-2]