Name
Abstract | ||
|---|---|---|
Motivated by reasoning tasks for XML languages, the satisfiability problem of logics on data trees is investigated. The nodes of a data tree have a label from a finite set and a data value from a possibly infinite set. It is shown that satisfiability for two-variable first-order logic is decidable if the tree structure can be accessed only through the child and the next sibling predicates and the access to data values is restricted to equality tests. From this main result, decidability of satisfiability and containment for a data-aware fragment of XPath and of the implication problem for unary key and inclusion constraints is concluded. |
Year | DOI | Venue |
|---|---|---|
2009 | 10.1145/1516512.1516515 | J. ACM |
Keywords | Field | DocType |
satisfiability problem,XML language,Two-variable logic,data-aware fragment,tree structure,data tree,consistency,integrity constraints,xml,data value,finite set,infinite set,implication problem,XML reasoning,implications,equality test,dtds | Discrete mathematics,Finite set,XML,Computer science,Tree (data structure),Boolean satisfiability problem,Theoretical computer science,Data integrity,Data value | Journal |
Volume | Issue | ISSN |
56 | 3 | 0004-5411 |
Citations | PageRank | References |
71 | 2.24 | 28 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Mikoaj Bojańczyk | 1 | 71 | 2.24 |
| Anca Muscholl | 2 | 1179 | 74.92 |
| Thomas Schwentick | 3 | 2373 | 155.10 |
| Luc Segoufin | 4 | 1453 | 153.14 |