Search

• < Previous
• 1
• Next >

---

On the complexity of XPath containment in the presence of disjunction, DTDs, and variables

Frank Neven ; Thomas Schwentick.

XPath is a simple language for navigating an XML-tree and returning a set of answer nodes. The focus in this paper is on the complexity of the containment problem for various fragments of XPath. We restrict attention to the most common XPath expressions which navigate along the child and/or&nbsp;[&hellip;]

---

A note on the expressive power of linear orders

Thomas Schwentick ; Nicole Schweikardt.

This article shows that there exist two particular linear orders such that first-order logic with these two linear orders has the same expressive power as first-order logic with the Bit-predicate FO(Bit). As a corollary we obtain that there also exists a built-in permutation such that first-order&nbsp;[&hellip;]

---

Rewriting with Acyclic Queries: Mind Your Head

Gaetano Geck ; Jens Keppeler ; Thomas Schwentick ; Christopher Spinrath.

The paper studies the rewriting problem, that is, the decision problem whether, for a given conjunctive query $Q$ and a set $\mathcal{V}$ of views, there is a conjunctive query $Q'$ over $\mathcal{V}$ that is equivalent to $Q$, for cases where the query, the views, and/or the desired rewriting are&nbsp;[&hellip;]

---