Analysis of imperative XML programs

Research output: Chapter in Book/Report/Conference proceedingBook chapter


The widespread adoption of XML has led to programming languages that support XML as a first class construct. In this paper, we present a method for analyzing and optimizing imperative XML processing programs. In particular, we present a program analysis, based on a flow-sensitive type system, for detecting both redundant computations and redundant traversals in XML processing programs. The analysis handles declarative queries over XML data and imperative loops that traverse XML values explicitly in a uniform framework. We describe two optimizations that take advantage of our analysis: one merges queries that traverse the same set of XML nodes, and the other replaces an XPath expression by a previously computed result. We show the effectiveness of our method by providing performance measurements on XMark benchmark queries and XLinq sample queries.


External organisations
  • IBM Thomas J. Watson Research Center
  • University of Colorado
Research areas and keywords

Subject classification (UKÄ) – MANDATORY

  • Computer Science


  • Typing Rule, Type Environment, Loop Body, Redundant Computation, XPath Expression
Original languageEnglish
Title of host publicationDatabase Programming Languages
Subtitle of host publication11th International Symposium, DBPL 2007, Revised Selected Papers
Number of pages15
ISBN (Electronic)978-3-540-75987-4
ISBN (Print)9783540759867
Publication statusPublished - 2007 Dec 1
Publication categoryResearch
Externally publishedYes
Event11th International Symposium on Database Programming Languages, DBPL 2007 - Vienna, Austria
Duration: 2007 Sep 232007 Sep 24

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume4797 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference11th International Symposium on Database Programming Languages, DBPL 2007