Download Now Free registration required
The authors address the cost of adding value joins to tree-pattern queries and monadic second-order queries over trees in terms of the tractability of query evaluation over two data models: XML and probabilistic XML. Their results show that the data complexity rises from linear, for join-free queries, to intractable, for queries with value joins, while combined complexity remains essentially the same. For Tree-Pattern queries with Joins (TPJ) the complexity jump is only on probabilistic XML, while for Monadic Second-Order logic over trees with Joins (TMSOJ) it already appears for deterministic XML documents.
- Format: PDF
- Size: 526 KB