Finite Satisfiability of Key and Foreign Key Constraints for XML Data


Key and foreign key constraints are useful for XML in semantic specification,
query optimization and more importantly, for information preservation when
exchanging data originating in legacy databases. Several XML proposals, e.g., 
XML Schema and XML Data, support key and foreign key specifications. These 
constraints, however, may not be finitely satisfiable in the XML context. More
specifically, given a DTD D and a finite set S of key and foreign key
constraints, there may not exist finite  XML documents that both conform to 
D and satisfy constraints of S. This paper investigates the finite 
satisfiability problem associated with key and foreign key constraints for XML.
We show that DTDs  impose a class of cardinality constraints on XML documents,
and these cardinality constraints interact with key and foreign key 
constraints. We investigate the interaction and establish PTIME decidability 
for determining finite satisfiability of key and foreign key constraints
for XML.