Abstract:
Modern Web developers must often process collections of XML data that are aggregated from potentially thousands of heterogeneous sources. While the semi-structured nature of XML provides a high degree of syntactic flexibility there are significant shortcomings to specify the semantics of its data. For the advancement of XML applications it is therefore an important problem to identify natural classes of constraints that can be utilized effectively by XML data engineers. The problem is challenging given the range of intractability results in the area. In this paper we propose a class of XML cardinality constraints that is sufficiently flexible to process concisely XML data from various sources. The flexibility is a result of the right balance between expressiveness and efficiency of maintenance. In particular, we characterize the associated implication problem axiomatically, and algorithmically by a low-degree polynomial time decision procedure. Our class is precious as small extensions in expressiveness result in intractability.
