Software

Value Joins Are Expensive Over (Probabilistic) XML

Date Added: Mar 2011
Format: PDF

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.