Internet Management Research Department, Bell Labs
Deptartment of Computer and Information Sciences, Temple University
4pm Tuesday 26th February 2002
Room 2511, JCMB, King's Buildings
A specification for XML data typically consists of a type (DTD) and a set of integrity constraints. Such an XML specification, however, may not be consistent, i.e., there exists no XML document that both satisfies the constraints and conforms to the DTD. With this comes the need to verify the consistency of XML specifications at compile-time. A closely related question is implication: suppose it is known that a set of constraints is satisfied by an XML document conforming to a DTD, does it follow that the document must also satisfy some other constraint? These issues are important in XML specifications, transformations, integration, and management.
This talk presents our recent results in connection with the consistency analysis of XML specifications. We investigate specifications defined with DTDs and a variety of constraint languages important for XML data: absolute, relative and regular keys and foreign keys. We show that in contrast to the triviality of its relational counterpart, the analysis of XML specifications is highly intricate. Even for restricted constraints and DTDs, the complexity ranges from NP-hard to undecidable. We also establish complexity results for the implication analysis of XML constraints.
(Joint work with Leonid Libkin and Marcelo Arenas, Univ. of Toronto)