Projects per year
Abstract / Description of output
Data trees provide a standard abstraction of XML documents with data values: they are trees whose nodes, in addition to the usual labels, can carry labels from an infinite alphabet (data). Therefore, one is interested in decidable formalisms for reasoning about data trees. While some are known  such as the twovariable logic  they tend to be of very high complexity, and most decidability proofs are highly nontrivial. We are therefore interested in reasonable complexity formalisms as well as better techniques for proving decidability.
Here we show that many decidable formalisms for data trees are subsumed  fully or partially  by the power of tree automata together with set constraints and linear constraints on cardinalities of various sets of data values. All these constraints can be translated into instances of integer linear programming, giving us an NP bound on the complexity of the reasoning tasks. We prove that this bound, as well as the key encoding technique, remain very robust, and allow the addition of features such as counting of paths and patterns, and even a concise encoding of constraints, without increasing the complexity. We also relate our results to several reasoning tasks over XML documents, such as satisfiability of schemas and data dependencies and satisfiability of the twovariable logic.
Here we show that many decidable formalisms for data trees are subsumed  fully or partially  by the power of tree automata together with set constraints and linear constraints on cardinalities of various sets of data values. All these constraints can be translated into instances of integer linear programming, giving us an NP bound on the complexity of the reasoning tasks. We prove that this bound, as well as the key encoding technique, remain very robust, and allow the addition of features such as counting of paths and patterns, and even a concise encoding of constraints, without increasing the complexity. We also relate our results to several reasoning tasks over XML documents, such as satisfiability of schemas and data dependencies and satisfiability of the twovariable logic.
Original language  English 

Title of host publication  Database Theory  ICDT 2011, 14th International Conference 
Publisher  ACM 
Pages  1829 
Number of pages  12 
ISBN (Print)  9781450305297 
DOIs  
Publication status  Published  2011 
Fingerprint
Dive into the research topics of 'Efficient reasoning about data trees via integer linear programming'. Together they form a unique fingerprint.Projects
 1 Finished

XML with Incomplete Information: Representation, Querying and Applications
1/09/09 → 30/11/13
Project: Research
Prizes

2011 ICDT Best Paper Award
David, Claire (Recipient), Libkin, Leonid (Recipient) & Tan, Tony (Recipient), 24 Mar 2011
Prize: Prize (including medals and awards)