XML-constraints

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

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 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.

Files

• "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 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

• -t to show the resulting mini-tree
• -w to show the resulting witness-graph or cardinality network
• -m to show the marking set

Configuration

Contact

For further question about this project please do not hesitate to contact us:
Flavio Ferrarotti (flavio.ferrarottivuw.ac.nz)
Emir Muñoz (emir.munozie.fujitsu.com)

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