Article

Querying ontologies in relational database systems

Authors:

Silke Trißl,

Ulf LeserAuthors Info & Claims

DILS'05: Proceedings of the Second international conference on Data Integration in the Life Sciences

Pages 63 - 79

https://doi.org/10.1007/11530084_7

Published: 20 July 2005 Publication History

Publisher Site

Abstract

In many areas of life science, such as biology and medicine, ontologies are nowadays commonly used to annotate objects of interest, such as biological samples, clinical pictures, or species in a standardized way. In these applications, an ontology is merely a structured vocabulary in the form of a tree or a directed acyclic graph of concepts. Typically, ontologies are stored together with the data they annotate in relational databases. Querying such annotations must obey the special semantics encoded in the structure of the ontology, i.e. relationships between terms, which is not possible using standard SQL alone.

In this paper, we develop a new method for querying DAGs using a pre-computed index structure. Our new indexing method extends the pre-/ postorder ranking scheme, which has been studied intensively for trees, to DAGs. Using typical queries on ontologies, we compare our approach to two other commonly used methods, i.e., a recursive database function and the pre-computation of the transitive closure of a DAG.

We show that pre-computed indexes are an order of magnitude faster than recursive methods. Clearly, our new scheme is slower than usage of the transitive closure, but requires only a fraction of the space and is therefore applicable even for very large ontologies with more than 200,000 concepts.

References

[1]

DL Wheeler, C Chappey, AE Lash, DD Leipe, TL Madden, GD Schuler, TA Tatusova, and BA Rapp. Database resources of the National Center for Biotechnology Information. Nucleic Acids Research, 28(1):10 - 14, Jan 2000.

Crossref

Google Scholar

[2]

Gene Ontoloy Consortium. The Gene Ontology (GO) database and inforamtics resource. Nucleic Acids Research, 32:D258 - D261, 2004. Database issue.

Crossref

Google Scholar

[3]

P. Dietz and D. Sleator. Two algorithms for maintaining order in a list. In Proceedings of the nineteenth annual ACM conference on Theory of computing, pages 365-372. ACM Press, 1987.

Digital Library

Google Scholar

[4]

Torsten Grust. Accelerating XPath location steps. In Proceedings of the 2002 ACM SIGMOD international conference on Management of data, pages 109-120. ACM Press, 2002.

Digital Library

Google Scholar

[5]

Hongjun Lu. New strategies for computing the transitive closure of a database relation. In Proceedings of the 13th International Conference on Very Large Data Bases, pages 267-274. Morgan Kaufmann Publishers Inc., 1987.

Digital Library

Google Scholar

[6]

P. Valduriez and H. Boral. Evaluation of recursive queries using join indices. In L. Kerschberg, editor, First International Conference on Expert Database Systems, pages 271-293, Redwood City, CA, 1986. Addison-Wesley.

Google Scholar

[7]

Sabine Mayer, Torsten Grust, Maurice van Keulen, and Jens Teubner. An injection of tree awareness: Adding staircase join to postgresql. In Mario A. Nascimento, M. Tamer Özsu, Donald Kossmann, Renée J. Miller, José A. Blakeley, and K. Bernhard Schiefer, editors, VLDB, pages 1305-1308. Morgan Kaufmann, 2004.

Digital Library

Google Scholar

[8]

Zografoula Vagena, Mirella Moura Moro, and Vassilis J. Tsotras. Twig query processing over graph-structured xml data. In Sihem Amer-Yahia and Luis Gravano, editors, WebDB, pages 43-48, 2004.

Digital Library

Google Scholar

[9]

Rakesh Agrawal, Alexander Borgida, and H. V. Jagadish. Efficient management of transitive relationships in large data and knowledge bases. In James Clifford, Bruce G. Lindsay, and David Maier, editors, SIGMOD Conference, pages 253-262. ACM Press, 1989.

Digital Library

Google Scholar

[10]

Ralf Schenkel, Anja Theobald, and Gerhard Weikum. Efficient creation and incremental maintenance of the hopi index for complex xml document collections. In ICDE, 2005.

Digital Library

Google Scholar

[11]

Edith Cohen, Eran Halperin, Haim Kaplan, and Uri Zwick. Reachability and distance queries via 2-hop labels. SIAM J. Comput., 32(5):1338-1355, 2003.

Digital Library

Google Scholar

[12]

Andrew Y. Wu, Michael Garland, and Jiawei Han. Mining scale-free networks using geodesic clustering. In Won Kim, Ron Kohavi, Johannes Gehrke, and William DuMouchel, editors, KDD, pages 719-724. ACM, 2004.

Digital Library

Google Scholar

[13]

Xifeng Yan, Philip S. Yu, and Jiawei Han. Graph indexing: A frequent structure-based approach. In Gerhard Weikum, Arnd Christian König, and Stefan Deßloch, editors, SIGMOD Conference, pages 335-346. ACM, 2004.

Digital Library

Google Scholar

Cited By

View all

Andreasen TBulskov H(2009)Conceptual querying through ontologiesFuzzy Sets and Systems10.1016/j.fss.2009.02.019160:15(2159-2172)Online publication date: 1-Aug-2009
https://dl.acm.org/doi/10.1016/j.fss.2009.02.019
Trißl SLeser UZhou LLing TOoi B(2007)Fast and practical indexing and querying of very large graphsProceedings of the 2007 ACM SIGMOD international conference on Management of data10.1145/1247480.1247573(845-856)Online publication date: 11-Jun-2007
https://dl.acm.org/doi/10.1145/1247480.1247573
Andreasen TBulskov H(2007)On Browsing Domain Ontologies for Information Base ContentProceedings of the 12th international Fuzzy Systems Association world congress on Foundations of Fuzzy Logic and Soft Computing10.1007/978-3-540-72950-1_14(135-144)Online publication date: 18-Jun-2007
https://dl.acm.org/doi/10.1007/978-3-540-72950-1_14
Show More Cited By

Recommendations

The limits of querying ontologies
ICDT'07: Proceedings of the 11th international conference on Database Theory

We study query answering in Description Logics (DLs). In particular, we consider conjunctive queries, unions of conjunctive queries, and their extensions with safe negation or inequality, which correspond to well-known classes of relational algebra ...
Semantic Interoperability Between Relational Database Systems
IDEAS '07: Proceedings of the 11th International Database Engineering and Applications Symposium

Relational DataBase Systems (RDBSs) are well-known and widely used in many organizations, however, semantic conflicts between the participating RDBSs must be resolved before data can be exchanged between them. Semantic resolution between the RDBSs is ...
Querying Heterogeneous Relational Database using SPARQL
ICIS '09: Proceedings of the 2009 Eigth IEEE/ACIS International Conference on Computer and Information Science

The emergence of the Semantic Web has given rise to several researches on semantic integration of heterogeneous relational databases using ontology. This paper studies the query rewriting problem in such an integration scenario. RDF’s graph model lends ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

DILS'05: Proceedings of the Second international conference on Data Integration in the Life Sciences

July 2005

344 pages

ISBN:3540279679

Editors:
Bertram Ludäscher
Department of Computer Science, University of California, Davis
,
Louiqa Raschid
Department of Computer Science, University of Maryland, College Park, MD

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 20 July 2005

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

5
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 18 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

Andreasen TBulskov H(2009)Conceptual querying through ontologiesFuzzy Sets and Systems10.1016/j.fss.2009.02.019160:15(2159-2172)Online publication date: 1-Aug-2009
https://dl.acm.org/doi/10.1016/j.fss.2009.02.019
Trißl SLeser UZhou LLing TOoi B(2007)Fast and practical indexing and querying of very large graphsProceedings of the 2007 ACM SIGMOD international conference on Management of data10.1145/1247480.1247573(845-856)Online publication date: 11-Jun-2007
https://dl.acm.org/doi/10.1145/1247480.1247573
Andreasen TBulskov H(2007)On Browsing Domain Ontologies for Information Base ContentProceedings of the 12th international Fuzzy Systems Association world congress on Foundations of Fuzzy Logic and Soft Computing10.1007/978-3-540-72950-1_14(135-144)Online publication date: 18-Jun-2007
https://dl.acm.org/doi/10.1007/978-3-540-72950-1_14
Faulstich LLeser UVitt T(2006)Implementing a linguistic query language for historic textsProceedings of the 2006 international conference on Current Trends in Database Technology10.1007/11896548_45(601-612)Online publication date: 26-Mar-2006
https://dl.acm.org/doi/10.1007/11896548_45
Gupta ASantini S(2006)On querying OBO ontologies using a DAG pattern query languageProceedings of the Third international conference on Data Integration in the Life Sciences10.1007/11799511_14(152-167)Online publication date: 20-Jul-2006
https://dl.acm.org/doi/10.1007/11799511_14

Abstract

References

Cited By

Recommendations

The limits of querying ontologies

Semantic Interoperability Between Relational Database Systems

Querying Heterogeneous Relational Database using SPARQL

Comments

Information

Published In

Sponsors

Publisher

Publication History

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations