Informatics Report Series



Related Pages

Report (by Number) Index
Report (by Date) Index
Author Index
Institute Index

Title:On XML integrity constraints in the presence of DTDs
Authors: Wenfei Fan ; Leonid Libkin
Date:May 2002
Publication Title:Journal of the ACM (JACM)
Publication Type:Journal Article Publication Status:Published
Volume No:49(3) Page Nos:368-406
The paper 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.
Links To Paper
The ACM Digital Library
Bibtex format
author = { Wenfei Fan and Leonid Libkin },
title = {On XML integrity constraints in the presence of DTDs},
journal = {Journal of the ACM (JACM)},
publisher = {ACM},
year = 2002,
month = {May},
volume = {49(3)},
pages = {368-406},
doi = {10.1145/567112.567117},
url = {},

Home : Publications : Report 

Please mail <> with any changes or corrections.
Unless explicitly stated otherwise, all material is copyright The University of Edinburgh