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

Ferrarotti, Flavio
Hartmann, Sven
Link, Sebastian
Marin, Mauricio
Muñoz, Emir
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
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.
Springer Verlag
Publisher DOI
Attribution-NonCommercial-NoDerivs 3.0 Ireland