Analysis of Imperative XML Programs

Authors: Michael G. Burke, Igor Peshansky, Mukund Raghavachari, and Christoph Reichenbach

Conference: 11th International Symposium on Database Programming Languages (DBPL 2007), Vienna, Austria, September 23-24, 2007

Abstract: 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.

Download: postscript file (319K), PDF file (251K)

BibTeX Entry:

@INPROCEEDINGS{burke-peshansky-raghavachari-07,
  Author      = {Michael G. Burke and Igor Peshansky and Mukund Raghavachari
                 and Christoph Reichenbach},
  Title       = "Analysis of Imperative {XML} Programs",
  Booktitle   = "11th International Symposium on Database Programming
                 Languages (DBPL2007)",
  Pages       = "216--230",
  Year        = "2007",
  Month       = "September",
  Day         = "23--24",
  Location    = "Vienna, Austria",
  Publisher   = "Springer",
  ISBN        = "3-540-75986-7",
}

[Home]

Last modified on
Igor Peshansky
pechtcha@cs.nyu.edu