View on GitHub


XML-constraints projects

download .ZIPdownload .TGZ

WISE 2013

This repository contains the resources used in the experiments of the paper "Soft Cardinality Constraints on XML Data" for WISE2013.

On-line version of the paper


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 characterize 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 and where exceptions to common rules frequently occur.


(Note: For now we only leave available executable versions for the applications.)

How to run

If you want to run our implementations execute the following commands in a console:

./xmlkeys -f constraints-dataset/tmp.keys -l label
./max-const -f constraints-dataset/tmp.softmax -l label

where label is the fixed replacement label. The final response for both applications is a true if the first constraint (first line) in tmp file is implied by the following constraints; or false otherwise.

Other options


The experiments were executed in a Intel Core i7 2.8 GHz machine, with 4 GB of RAM, running a 64 bits Linux kernel 2.6.32. We compiled our C++ implementation of the algorithms using the standard g++ compiler from the GNU Compiler Collection 4.6.3.


For further question about this project please do not hesitate to contact us:
Flavio Ferrarotti (
Emir Muñoz (

Emir Muñoz
Fujitsu Ireland Ltd.
National University of Ireland
Galway, Ireland