Edinburgh Research Explorer

What's Hard about XML Schema Constraints?

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Original languageEnglish
Title of host publicationDatabase and Expert Systems Applications
Subtitle of host publication13th International Conference, DEXA 2002, Aix-en-Provence, France, September 2-6, 2002, Proceedings
PublisherSpringer Berlin Heidelberg
Pages269-278
Number of pages10
Volume2453
ISBN (Electronic)978-3-540-46146-3
ISBN (Print)978-3-540-44126-7
DOIs
Publication statusPublished - 2002

Abstract

Data description for XML usually comes in the form of a type specification (e.g., a DTD) together with integrity constraints. XML Schema allows one to mix DTD features with semantic information, such as keys and foreign keys. It was shown recently [[2],[7]] that the interaction of DTDs with constraints may be rather nontrivial. In particular, testing if a general specification is consistent is undecidable, but for the most common case of single-attribute constraints it is NP-complete, and linear time if no foreign keys are present.

However, XML Schema design did not adopt the form of constraints prevalent in the database literature, and slightly changed the semantics of keys, foreign keys, and unique constraints. In this paper we demonstrate the very costly effect of this slight change on the feasibility of consistency checking. In particular, all the known hardness results extend to the XML Schema case, but tractability results do not. We show that even without foreign keys, and with very simple DTD features, checking consistency of XML-Schema specifications is intractable.

ID: 19849521