The building of BODHI, a bio-diversity database system

Srikanta J. Bedathur, Jayant R. Haritsa, Uday S. Sen

TL;DR

This paper introduces BODHI, an object-oriented database system designed to integrate diverse biological data types—taxonomy, spatial distribution, and genetic sequences—into a single, queryable platform. By leveraging open-source components and novel indexing strategies, BODHI aims to streamline complex bio-diversity research and provide a robust testbed for new data management techniques.

What Problem Does This Paper Address?

Modern biological research, particularly in bio-diversity, is increasingly interdisciplinary, requiring the integration of data from various sources and scales. This includes everything from the hierarchical classification of species (taxonomy) and their geographical locations (spatial data) to their genetic makeup (DNA and protein sequences). Traditionally, researchers have had to use disparate tools and databases for each data type, making it incredibly difficult and time-consuming to perform cross-domain queries. For example, answering a question about which fruit-bearing shrubs share habitats and possess specific genetic similarities would involve manually piecing together results from multiple, independent systems. This fragmentation hinders the discovery of complex patterns and relationships crucial for understanding bio-diversity.

Methods

BODHI is built upon an object-oriented modeling approach, allowing it to naturally represent the complex, hierarchical, and interconnected nature of biological data. Key technical components include:

  • SHORE Storage Manager: A robust, open-source storage manager providing essential database functionalities like transaction management, logging, and recovery.
  • A-DB Query Optimizer: An extensible, rule-based query optimizer that handles query transformation and optimization, crucial for efficient execution plans.
  • Novel Indexing Strategies: To address the unique challenges of bio-diversity data, BODHI employs specialized indexing techniques:
  • Path Dictionary: For efficient traversal of aggregation hierarchies (e.g., Order-Family-Genus-Species).
  • Multi-key Type Indexing (MT-index): For indexing inheritance hierarchies.
  • Hilbert R-Tree: An enhancement over the standard R*-Tree for efficient spatial data indexing, particularly in dynamic environments.
  • Service Modules: Dedicated modules for Object Services, Spatial Services, and Sequence Services, each tailored to handle specific data types and operations.
  • Extensible Type System: Spatial and sequence data types are provided as user-level libraries, allowing for easier modification and extension by database administrators.

Datasets

The paper utilizes a combination of synthetic and real datasets for evaluation:

  • Synthetic Dataset: Generated to conform to the BODHI object model, including taxonomy, spatial regions (rectangular), and DNA sequences. This dataset was augmented with a small subset of real plant data.
  • Sequoia 2000 Benchmark: A standard benchmark for spatial databases, used to evaluate BODHI's spatial data handling capabilities. The vector portion of this benchmark (points, polygons, graphs) was used, excluding raster data.
  • EMBL GenBank: Publicly available "expressed sequence tags" (ESTs) were used to populate the genome sequence data.

Key Insights and Ideas

  • Integrated Bio-diversity Data Management is Crucial: The paper strongly argues for a unified approach to managing diverse biological data, highlighting the limitations of fragmented systems.
  • Object-Oriented Modeling is a Natural Fit: The inherent complexity and hierarchical nature of bio-diversity data are well-suited to an object-oriented database model.
  • Specialized Indexing is Key: Standard indexing techniques are insufficient for the diverse data types. BODHI's success hinges on specialized indexes like the Path Dictionary and Hilbert R-Tree.
  • Spatial Operations are Expensive but Manageable: While spatial operations are computationally intensive, BODHI's indexing strategies make them feasible within a broader bio-diversity context.
  • Genomic Queries are the "Hard Nuts": Surprisingly, the paper identifies genomic sequencing queries as particularly challenging and expensive, suggesting a critical need for efficient indexing in this area.
  • Open-Source and Commodity Hardware are Viable: BODHI demonstrates that a powerful, integrated bio-diversity database can be built using readily available software and hardware, making it accessible to researchers with limited budgets.

Key Results

  • Significant Query Speedups: The Path Dictionary index provided orders-of-magnitude improvement for taxonomy queries involving aggregation path traversals.
  • Competitive Spatial Performance: BODHI's spatial query performance was comparable to the Paradise GIS system, a highly optimized spatial database, especially when using the R*-Tree index.
  • Hilbert R-Tree Performance: Initial results showed the Hilbert R-Tree performing worse than the R*-Tree due to lower packing factors, an area for further investigation.
  • Multi-domain Query Efficiency: Queries combining taxonomy and spatial data showed substantial improvements with the use of both Path Dictionary and R*-Tree indexes, indicating the value of integrated indexing.
  • BLAST Query Dominance: Multi-domain queries involving BLAST score computations were dominated by the sequence comparison time, underscoring the need for better genomic indexing.

Limitations and Future Work

  • Lack of Bulk Loading: BODHI currently lacks a bulk-loading feature, leading to higher data loading times compared to systems like Paradise. This is considered a minor bottleneck as bio-diversity databases are typically query-intensive.
  • Hilbert R-Tree Performance: The observed lower performance of the Hilbert R-Tree requires further investigation into the implementation and its packing factor.
  • Genomic Indexing: The paper explicitly calls for the development of efficient indexing strategies for genomic sequence data, as these queries are identified as major performance bottlenecks.
  • High-Dimensional Data Indexing: The authors are actively working on incorporating new indexing mechanisms, such as the Pyramid Tree, for high-dimensional data, which is common in areas like drug-related datasets.
  • Extensibility: While the type system is designed for extensibility, further work is needed to fully leverage this for complex data types and operations.

Summary updated

Abstract

We have recently built a database system called BODHI, intended to store plant bio-diversity information. It is based on an object-oriented modeling approach and is developed completely around public-domain software. The unique feature of BODHI is that it seamlessly integrates diverse types of data, including taxonomic characteristics, spatial distributions, and genetic sequences, thereby spanning the entire range from molecular to organism-level information. A variety of sophisticated indexing strategies are incorporated to efficiently access the various types of data, and a rule-based query processor is employed for optimizing query execution. In this paper, we report on our experiences in building BODHI and on its performance characteristics for a representative set of queries.
BibTeX
@inproceedings{bedathur2003building,
  author = {Srikanta J. Bedathur and Jayant R. Haritsa and Uday S. Sen},
  title = {{The building of BODHI, a bio-diversity database system}},
  booktitle = {Inf. Syst},
  year = {2003},
  url = {https://openreview.net/forum?id=FEdWX8QdiD},
}
Figure