The study of integrity constraints has been identified as one of the major challenges in XML database research. The main difficulty is finding a balance between the expressiveness and the existence of automated reasoning tools for different classes of constraints.
In this paper we define Boolean constraints for XML by exploring homomorphisms between XML data trees and XML schema graphs. These constraints are naturally exhibited by XML data due to its nested structure.
We demonstrate, in contrast to many other proposals, that reasoning about Boolean constraints is well-founded. That is, we establish that the interaction between Boolean constraints corresponds precisely to the logical implication of Boolean propositional formulae. Therefore, our Boolean constraints do not only capture valuable semantic information about XML data but also permit reasoning support by off-the-shelf SAT solvers. Finally, we identify a few subclasses of Boolean constraints for which the implication problem can be solved efficiently.
IOS Press, Inc.
6751 Tepper Drive
Clifton, VA 20124
Tel.: +1 703 830 6300
Fax: +1 703 830 2300 email@example.com
(Corporate matters and books only) IOS Press c/o Accucoms US, Inc.
For North America Sales and Customer Service
West Point Commons
Lansdale PA 19446
Tel.: +1 866 855 8967
Fax: +1 215 660 5042 firstname.lastname@example.org