MinMax Trees: Efficient Relational Operation Support for Hierarchical Data Exploration
Ionel D. Stroe, Elke Angelika Rundensteiner, Matthew O. Ward · 1999
This paper presents a new method for implementing hierarchical navigation operations in relational database systems as required for applications such as interactive visual explorations over large datasets. A particular class of recursive unions of joins and divisions that operate on hierarchies has been identified. By using adequate pre-computation (i.e., organizing the hierarchical structure as what we called a MinMax tree), the recursive processing of the operations in this class is shown to be reducible to range queries. Extensions of the method for non-tree as well as dynamic hierarchies have also been designed. We implemented our technique using Oracle 7 and C as a host language and showed that the MinMax method performed significantly faster than the equivalent recursive ones. Our method has been applied to implement navigation operations in XmdvTool, a visualization system for exploration of multivariate data.