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.