Satisfiability of downward XPath with data equality tests
D Figueira - Proceedings of the twenty-eighth ACM SIGMOD …, 2009 - dl.acm.org
Proceedings of the twenty-eighth ACM SIGMOD-SIGACT-SIGART symposium on …, 2009•dl.acm.org
In this work we investigate the satisfiability problem for the logic XPath (↓*,↓,=), that
includes all downward axes as well as equality and inequality tests. We address this
problem in the absence of DTDs and the sibling axis. We prove that this fragment is
decidable, and we nail down its complexity, showing the problem to be ExpTime-complete.
The result also holds when path expressions allow closure under the Kleene star operator.
To obtain these results, we introduce a new automaton model over data trees that captures …
includes all downward axes as well as equality and inequality tests. We address this
problem in the absence of DTDs and the sibling axis. We prove that this fragment is
decidable, and we nail down its complexity, showing the problem to be ExpTime-complete.
The result also holds when path expressions allow closure under the Kleene star operator.
To obtain these results, we introduce a new automaton model over data trees that captures …
In this work we investigate the satisfiability problem for the logic XPath(↓*, ↓,=), that includes all downward axes as well as equality and inequality tests. We address this problem in the absence of DTDs and the sibling axis. We prove that this fragment is decidable, and we nail down its complexity, showing the problem to be ExpTime-complete. The result also holds when path expressions allow closure under the Kleene star operator. To obtain these results, we introduce a new automaton model over data trees that captures XPath(↓*, ↓,=) and has an ExpTime emptiness problem. Furthermore, we give the exact complexity of several downward-looking fragments.
ACM Digital Library