Edinburgh Research Explorer

On XML integrity constraints in the presence of DTDs

Research output: Contribution to journalArticle

Related Edinburgh Organisations

Open Access permissions

Open

Documents

http://doi.acm.org/10.1145/567112.567117
Original languageEnglish
Pages (from-to)368-406
Number of pages39
JournalJournal of Virology
Volume49
Issue number3
DOIs
Publication statusPublished - 2002

Abstract

The article investigates XML document specifications with DTDs and integrity constraints, such as keys and foreign keys. We study the consistency problem of checking whether a given specification is meaningful: that is, whether there exists an XML document that both conforms to the DTD and satisfies the constraints. We show that DTDs interact with constraints in a highly intricate way and as a result, the consistency problem in general is undecidable. When it comes to unary keys and foreign keys, the consistency problem is shown to be NP-complete. This is done by coding DTDs and integrity constraints with linear constraints on the integers. We consider the variations of the problem (by both restricting and enlarging the class of constraints), and identify a number of tractable cases, as well as a number of additional NP-complete ones. By incorporating negations of constraints, we establish complexity bounds on the implication problem, which is shown to be coNP-complete for unary keys and foreign keys.

Download statistics

No data available

ID: 19849493