Humboldt-Universität zu Berlin - Mathematisch-Naturwissenschaftliche Fakultät - Wissensmanagement in der Bioinformatik

Forschungsseminar Sommersemester 2005

"Neue Entwicklungen in der Bioinformatik und Informationsintegration"


Silke Trißl

Anfragen an Ontologien in relationalen Datenbanken

Ontologien und Taxonomien sind kontrollierte, strukturierte Vokabulare für eine Domäne um Objekte darin zu beschreiben. Ontologien in der Biologie, wie beispielsweise die Gene Ontology oder die NCBI Taxonomie, die Klassifizierung von Lebewesen, sind als Bäume bzw. gerichtete, azyklische Graphen aufgebaut. Taxonomien werden häufig zusammen mit den annotierten Objekten in relationalen Datenbanken gespeichert.
Durch die Struktur der Ontologien bzw. Taxonomien können Beziehungen zwischen Objekten angefragt und erkannt werden. Diese Anfragen innerhalb eines relationalen Datenbanksystem auszuführen setzt entweder die Verwendung von rekursiven Funktionen oder die Indizierung des Graphen voraus. Ich stelle 2 verschiedene Indizierungsmöglichkeiten vor, die transitive Hülle und Pre- und Postorder Ranking, und vergleiche die Anfragezeiten für beide Indexstrukturen mit Anfragezeiten für die rekursive Funktion.