Prefiltering techniques for efficient XML document processing

ABSTRACT

Document Object Model (DOM) and Simple API for XML (SAX) are the two major programming models for XML document processing. Each, however, has its own efficiency limitation. DOM assumes an in-core representation of XML documents which can be problematic for large documents. SAX needs to scan over the document in a linear manner in order to locate the interesting fragments. Previously, we have used tree-to-table mapping and indexing techniques to help answer structural queries to large, or large collections of, XML documents. In this paper, we generalize the previous techniques into a prefiltering framework where repeated access to large XML documents can be efficiently carried out within the existing DOM and SAX models. The prefiltering framework essentially uses a tiny search engine to locate useful fragments in the target XML documents by approximately executing the user's queries. Those fragments are gathered into a candidate-set XML document, and is returned to the user's DOM- or SAX-based applications for further processing. This results in a practical and efficient model of XML processing, especially when the XML documents are large and infrequently updated, but are frequently being queried.

REFERENCES

• 1: A. Campillo, T. J. Green, A. Gupta, M. Onizuka, D. Raven, and D. Suciu. XMLTK: An XML toolkit for scalable XML stream processing. In Proc. of PLANX, 2002.
• 2: A. Slominski. Design of a Pull and Push Parser System for Streaming XML. Department of Computer Science, Indiana University, Technical Report TR550. 2001. Available: http://www.extreme.indiana.edu/xgws/papers/xml_push_pull.pdf
• 3: A. R. Schmidt , Florian Waas , Martin L. Kersten , D. Florescu , I. Manolescu , M. J. Carey , R. Busse, The XML benchmark project, CWI (Centre for Mathematics and Computer Science), Amsterdam, The Netherlands, 2001
• 4: Chia-Hsin Huang , Tyng-Ruey Chuang , Hahn-Ming Lee, Fast structural query with application to chinese treebank sentence retrieval, Proceedings of the 2004 ACM symposium on Document engineering, October 28-30, 2004, Milwaukee, Wisconsin, USA [doi>10.1145/1030397.1030400]
• 5: C. L. Chang, Y. H. Chang, T. R. Chuang, S. Ho, and F. T. Lin. Bridging Two Geography Languages: Experience in Mapping SEF to GML. In GML Dev Days: 2nd GML Developers Conference, 2003.
• 6: C.-Y. Chan , P. Felber , M. Garofalakis , R. Rastogi, Efficient filtering of XML documents with XPath expressions, The VLDB Journal — The International Journal on Very Large Data Bases, v.11 n.4, p.354-379, December 2002 [doi>10.1007/s00778-002-0077-6]
• 7: Danny Chen , Raymond K. Wong, Optimizing the lazy DFA approach for XML stream processing, Proceedings of the fifteenth Australasian database conference, p.131-140, January 01, 2004, Dunedin, New Zealand
• 8: D. Megginson. SAX: A Simple API for XML. Available: http://www.saxproject.org/
• 9: Dan Olteanu , Holger Meuss , Tim Furche , François Bry, XPath: Looking Forward, Proceedings of the Worshops XMLDM, MDDE, and YRWS on XML-Based Data Management and Multimedia Engineering-Revised Papers, p.109-127, March 24-28, 2002
• 10: DOM, World Wide Web Consortium. Document Object Model (DOM), W3C Recommendation.
• 11: J. Ferraiolo, editor, Scalable Vector Graphics (SVG) 1.0 Specification, W3C Recommendation, 2001.
• 12: K. J. Chen, C. C. Luo, Z. M. Gao, M. C. Chang, F. Y. Chen, C. J. Chen, and C. R. Huang. The CKIP Chinese Treebank. In Journees ATALA sur les Corpus annotes pour la syntaxe, Talana, Paris VII, 1999.
• 13: Mehmet Altinel , Michael J. Franklin, Efficient Filtering of XML Documents for Selective Dissemination of Information, Proceedings of the 26th International Conference on Very Large Data Bases, p.53-64, September 10-14, 2000
• 14: XRel: a path-based approach to storage and retrieval of XML documents using relational databases, ACM Transactions on Internet Technology (TOIT), v.1 n.1, p.110-141, Aug. 2001 [doi>10.1145/383034.383038]
• 15: Quanzhong Li , Bongki Moon, Indexing and Querying XML Data for Regular Path Expressions, Proceedings of the 27th International Conference on Very Large Data Bases, p.361-370, September 11-14, 2001
• 16: Qinghua Zou , Shaorong Liu , Wesley W. Chu, Ctree: a compact tree for indexing XML data, Proceedings of the 6th annual ACM international workshop on Web information and data management, November 12-13, 2004, Washington DC, USA [doi>10.1145/1031453.1031462]
• 17: Roy Goldman , Jennifer Widom, DataGuides: Enabling Query Formulation and Optimization in Semistructured Databases, Proceedings of the 23rd International Conference on Very Large Data Bases, p.436-445, August 25-29, 1997
• 18: Sihem Amer-Yahia , Laks V. S. Lakshmanan , Shashank Pandit, FleXPath: flexible structure and full-text querying for XML, Proceedings of the 2004 ACM SIGMOD international conference on Management of data, June 13-18, 2004, Paris, France [doi>10.1145/1007568.1007581]
• 19: S. Cox, P. Daisey, R. Lake, C. Portele, and A. Whiteside, editors. OpenGIS© Geography Markup Language (GML) Implementation Specification, Version: 3.00, 2003.
• 20: Torsten Grust , Maurice Van Keulen , Jens Teubner, Accelerating XPath evaluation in any RDBMS, ACM Transactions on Database Systems (TODS), v.29 n.1, p.91-131, March 2004 [doi>10.1145/974750.974754]
• 21: XML Fragment Interchange (Candidate Recommendation), World Wide Web Consortium.
• 22: XPath, World Wide Web Consortium. XML Path Language (XPath). W3C Recommendation.
• 23: XPointer, World Wide Web Consortium. XML Pointer Language (XPointer), W3C working Draft.
• 24: XQuery, World Wide Web Consortium. XML Query (XQuery). W3C Recommendation.
• 25: XSLT, World Wide Web Consortium. The Extensible Stylesheet Language Transformations (XSLT). W3C.
• 26: YFilter: Efficient and Scalable Filtering of XML Documents, Proceedings of the 18th International Conference on Data Engineering, p.341, February 26-March 01, 2002

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Pattern matching

Additional Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval
          Subjects: Search process

General Terms:
Algorithms, Performance

Keywords:
DOM, SAX, prefiltering, structural query, two-phased XML processing model