Value Joins Are Expensive Over (Probabilistic) XML

Download Now Free registration required

Executive Summary

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