Abstract | ||
---|---|---|
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. |
Year | Venue | Keywords |
---|---|---|
2008 | European Journal of Combinatorics | reasoning support,logical implication,boolean propositional formula,xml data tree,boolean constraint,xml schema graph,boolean constraints,xml data,xml modeling,automated reasoning tool,implication problem,xml database research,propositional logic,semantics,modeling,xml |
Field | DocType | Citations |
Boolean function,Boolean circuit,XML validation,Document Structure Description,XML database,Theoretical computer science,XML schema,Standard Boolean model,Boolean expression,Mathematics | Conference | 1 |
PageRank | References | Authors |
0.34 | 17 | 3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Sven Hartmann | 1 | 90 | 4.96 |
Sebastian Link | 2 | 462 | 39.59 |
Thu Trinh | 3 | 86 | 5.51 |