Efficient query evaluation for DAG-shaped hierarchies

This paper focuses on the use of labeling schemes for evaluating queries on DAG structured data, such as pedigrees and ontologies that are stored in a relational database. We compare using Dewey⁺ labeling, NodeCodes and its variants for the evaluation of ancestor/descendant queries on ontologies and inbreeding coefficient calculation on pedigrees. Ancestor/descendant queries can be answered based on the existence of the paths between nodes, while inbreeding coefficient calculations require the complete path information. While Dewey⁺ performs slightly better for descendant queries for DAGs with low selectivity, it cannot be used to evaluate queries requiring path information, e.g. inbreeding coefficient queries for pedigrees. NodeCodes enable evaluation of both types of queries (requiring path information, and ancestor/descendant queries) efficiently.