Finite Satisfiability of Key and Foreign Key Constraints for XML Data


Key and foreign key constraints are useful for XML data in semantic 
specification, query optimization and more importantly, for information 
preservation in data exchange. 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 \Sigma of key and foreign key 
constraints, there may not exist any finite XML documents that both conform 
to D and satisfy \Sigma. This paper investigates finite satisfiability 
problems associated with a class L_u of 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 L_u constraints.
We investigate the interaction and establish complexity results for the 
analysis of finite satisfiability of L_u constraints.  We show that it is 
NP-complete to determine, given any DTD D and any finite set \Sigma of 
L_u constraints over D, whether there is a finite XML document that both 
conforms to D and satisfies \Sigma. We also establish PTIME decidability for 
several special cases of the finite satisfiability problem.