XML with data values: Typechecking revisited

N. Alon, T. Milo, F. Neven, D. Suciu, V. Vianu

Research output: Contribution to conferencePaperpeer-review

29 Scopus citations


We investigate the typechecking problem for XML queries: statically verifying that every answer to a query conforms to a given output DTD, for inputs satisfying a given input DTD. This problem had been studied by a subset of the authors in a simplified framework that captured the structure of XML documents but ignored data values. We revisit here the typechecking problem in the more realistic case when data values are present in documents and tested by queries. In this extended framework, typechecking quickly becomes undecidable. However, it remains decidable for large classes of queries and DTDs of practical interest. The main contribution of the present paper is to trace a fairly tight boundary of decidability for typechecking with data values. The complexity of typechecking in the decidable cases is also considered.

Original languageEnglish (US)
Number of pages12
StatePublished - 2001
Externally publishedYes
Event20th ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems - Santa Barbara, CA, United States
Duration: May 21 2001May 23 2001


Other20th ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems
Country/TerritoryUnited States
CitySanta Barbara, CA

All Science Journal Classification (ASJC) codes

  • Software
  • Information Systems
  • Hardware and Architecture


Dive into the research topics of 'XML with data values: Typechecking revisited'. Together they form a unique fingerprint.

Cite this