Bilkent University
Department of Computer Engineering


Querying Pedigree Data and Evaluation of Pedigree Queries


Prof. Dr. Meral Özsoyoğlu
Case Western Reserve University

Genealogy information is becoming increasingly abundant in light of modern genetics and the study of diseases and risk factors. As the volume of this structured pedigree data expands, there is a pressing need for better ways to manage, store, and efficiently query this data. Building on recent advances in semi-structured data management and proven relational database technology, we propose a general-purpose Pedigree Query Language (PQL) for querying pedigree data, and a framework for efficient evaluation of pedigree queries. We describe how the problem of modeling and querying pedigree data differs from XML, and present an overview of PQL. We consider pedigree data structured in the form of a directed acyclic graph, and use an encoding scheme, called NodeCodes, for expediting the evaluation of queries on pedigree graph structures. Pedigree query evaluation using NodeCodes is implemented and tested using real data. Experimental results show that using NodeCodes provides a good alternative for pedigree query evaluation, with significant performance improvements for complex queries (>850%) over naive evaluation.


DATE: October 2, 2006, Monday @ 13:40