Soft cardinality constraints on XML data: How exceptions prove the business rule

Ferrarotti F., Hartmann S., Link S., Marin M., Muñoz E. (2013) Soft Cardinality Constraints on XML Data. In: Lin X., Manolopoulos Y., Srivastava D., Huang G. (eds) Web Information Systems Engineering – WISE 2013. WISE 2013. Lecture Notes in Computer Science, vol 8180. Springer, Berlin, Heidelberg

Abstract

We introduce soft cardinality constraints which need to be satisfied on average only, and thus permit violations in a controlled manner. Starting from a highly expressive but intractable class, we establish a fragment that is maximal with respect to both expressivity and efficiency. More precisely, we characterise the associated implication problem axiomatically and develop a low-degree polynomial time decision algorithm. Any increase in expressivity of our fragment results in coNP-hardness of the implication problem. Finally, we extensively test the performance of our algorithm. The performance evaluation provides first-hand evidence that reasoning about expressive notions of soft cardinality constraints on XML data is practically efficient and scales well. Our results unleash soft cardinality constraints on real-world XML practice, where a little more semantics makes applications a lot more effective in contexts where exceptions to common rules may occur.

Funder

|~|1267880|~|

Publisher

Springer Verlag

Rights

Attribution-NonCommercial-NoDerivs 3.0 Ireland

cbn

Collections

Data Science Institute (Scholarly Articles)