Efficient Processing of Multiple Structural Join Queries

摘要

XML is widely used for representing and exchanging hierarchical data and queries naturally specify hierarchical patterns to select relevant parts of an XML document. These patterns have a sequence of selection predicates connected by operators representing parent-child or ancestor-descendant relationships. In this context, the operation of structural join involves discovering pairs of nodes that are in ancestor-descendant relationship from the cross product of two sets of nodes. In this paper, we propose a novel way of solving queries with multiple structural joins by maintaining an extra piece of information for each element called nDe.sc, which specifies the number of descendants having same tag name as that of the element. An extensive experimental evaluation of our algorithms with datasets of varying nDesc value shows that our algorithms perform better than the currently existing join algorithms.