Interaction between path and type constraints

XML [7], which is emerging as an important standard for data exchange on the World-Wide Web, highlights the importance of semistructured data. Although the XML standard itself does not require any schema or type system, a number of proposals [6, 17, 19] have been developed that roughly correspond to data deni-tion languages. These allow one to constrain the struc-ture of XML data by imposing a schema on it. These and other proposals also advocate the need for integrity constraints, another form of constraints that should, for example, be capable of expressing inclusion constraints and inverse relationships. The latter have recently been studied as path constraints in the context of semistruc-tured data [4, 9]. It is likely that future XML proposals will involve both forms of constraints, and it is there-fore appropriate to understand the interaction between them. This paper investigates that interaction. In partic-ular it studies constraint implication problems, which are important both in understanding the semantics of type/constraint systems and in query optimization. A number of results on path constraint implication are es-tablished in the presence and absence of type systems. These results demonstrate that adding a type system may in some cases simplify reasoning about path con-straints and in other cases make it harder. For example, it is shown that there is a path constraint implication problem that is decidable in PTIME in the untyped con-text, but that becomes undecidable when a type system is added. On the other hand, there is an implication problem that is undecidable in the untyped context, but becomes not only decidable in cubic time but also nitely axiomatizable when a type system is imposed.