Holistically processing XML twig queries with AND, OR, and NOT predicates

Structural joins are important for XML queries, but suffer from producing large, unused intermediate result sets. Holistic twig joins claim to solve this problem, but previously proposed algorithms fail to support XML queries involving all the three types of logical operations predicates: AND, OR, and NOT, which are however highly desired (such queries are referred to as All-twigs). Currently, there is no holistic twig join algorithm designed for All-twigs. In this paper, we first propose to normalize All-twigs to harness their complexity and then present a holistic join framework based on normalized All-twigs.