This repository contains the resources used in the experiments of the paper "Soft Cardinality Constraints on XML Data" for WISE2013.
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.
- "constraints-dataset" folder contains all the sets of constraints used in the decision problem.
- "xmlkeys" is the application to decide the implication problem over XML keys.
- "max-const" is the application to decide the implication problem over Soft-max constraints.
- "xml-constraints-implication-WWW2013.xls" is an excel file with all the results obtained deciding the implication problem.
(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 labelor,
./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.
- -t to show the resulting mini-tree
- -w to show the resulting witness-graph or cardinality network
- -m to show the marking set
ConfigurationThe 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.
Fujitsu Ireland Ltd.
National University of Ireland