No CrossRef data available.
Article contents
Query evaluation and optimization in the semantic web
Published online by Cambridge University Press: 01 May 2008
Abstract
Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.
We address the problem of answering Web ontology queries efficiently. An ontology is formalized as a deductive ontology base (DOB), a deductive database that comprises the ontology's inference axioms and facts. A cost-based query optimization technique for DOB is presented. A hybrid cost model is proposed to estimate the cost and cardinality of basic and inferred facts. Cardinality and cost of inferred facts are estimated using an adaptive sampling technique, while techniques of traditional relational cost models are used for estimating the cost of basic facts and conjunctive ontology queries. Finally, we implement a dynamic-programming optimization algorithm to identify query evaluation plans that minimize the number of intermediate inferred facts. We modeled a subset of the Web ontology language Lite as a DOB and performed an experimental study to analyze the predictive capacity of our cost model and the benefits of the query optimization technique. Our study has been conducted over synthetic and real-world Web ontology language ontologies and shows that the techniques are accurate and improve query performance.
Information
- Type
- Regular Papers
- Information
- Copyright
- Copyright © Cambridge University Press 2008
References
Bruijn, J., Polleres, A. and Fensel, D. 2004. OWL Lite- WSML working draft. DERI Institute. http://www.wsmo.org/2004/d20/v0.1/20040629/.Google Scholar
Calvanese, D., Giacomo, G. D., Lembo, D., Lenzerini, M. and Rosati, R. 2005. Tailoring OWL for data intensive ontologies. In Proc. of Workshop on OWL: Experiences and Directions. CEUR-WS.ORG.Google Scholar
Eiter, T., Ianni, G., Schindlauer, R. and Tompits, H. 2006. Towards efficient evaluation of HEX-programs. In Proc. of NMR International Workshop on Non-Monotonic Reasoning.Google Scholar
Grosof, B., Horrocks, I., Volz, R. and Decker, S. 2003. Description logic programs: Combining logic programs with description logic. In Proc. of WWW International World Wide Web Conference. ACM Press, USA.CrossRefGoogle Scholar
Haarslev, V. and Moller, R. 2004. Optimization techniques for retrieving resources described in OWL/RDF documents: First results. In Proc. of KR Knowledge Reasoning Conference. AAAI Press, USA.Google Scholar
Horrocks, I. and Turi, D. 2005. The OWL instance store: System description. In Proc. of CADE International Conference on Automated Deduction. Springer, 177–181.Google Scholar
Hustadt, U. and Motik, B. 2005. Description logics and disjunctive datalog: The story so far. In Proc. of DL International Workshop on Description Logics. CEUR-WS.ORG.Google Scholar
Ling, Y. and Sun, W. 1992. A Supplement to sampling-based methods for query size estimation in a database system. SIGMOD Record 21, 4, 12–15.CrossRefGoogle Scholar
Lipton, R. and Naughton, J. 1990. Query size estimation by adaptive sampling (Extended Abstract). In Proc. of ACM SIGMOD International Conference on Management of Data. ACM Press, USA, 40–46.Google Scholar
Lipton, R., Naughton, J. and Schneider, D. 1990. Practical selectivity estimation through adaptive sampling. In Proc. of ACM SIGMOD International Conference on Management of Data. ACM Press, USA, 1–10.Google Scholar
McGuinness, D. and Harmelen, F. V. 2004. OWL Web ontology language overview. http://www.w3.org/tr/owl-features/.Google Scholar
Motik, B., Volz, R. and Maedche, A. 2003. Optimizing query answering in description logics using disjunctive deductive databases. In Proc. of KRDB International Workshop on Knowledge Representation meets Databases. CEUR-WS.ORG, 39–50.Google Scholar
Open Clinical Organization. 2001. GALEN common reference model. http://www.openclinical.org/.Google Scholar
Pan, Z. and Hefflin, J. 2003. DLDB: Extending relational databases to support semantic web queries. In Proc. of PSSS Workshop on Practical and Scalable Semantic Systems. CEUR-WS.ORG.CrossRefGoogle Scholar
Protege, Staff. 1999. Protege OWL: Ontology editor for the semantic web. http://protege.stanford.edu/plugins/owl/owl-library/.Google Scholar
Ramakrishnan, R. and Ullman, J. D. 1993. A survey of research on deductive database systems. Journal of Logic Programming. Elsevier, The Netherland, 23, 2, 125–149.CrossRefGoogle Scholar
Selinger, P., Astrahan, M., Chamberlin, D., Lorie, R. and Price, T. 1979. Access path selection in a relational database management system. In Proc. of ACM SIGMOD International Conference on Management of Data. ACM Press, USA, 23–34.Google Scholar
Sirin, E. and Parsia, B. 2006. Optimizations for answering conjunctive abox queries. In Proc. of DL International Workshop on Description Logics. CEUR-WS.ORG.Google Scholar
Staudt, M., Soiron, R., Quix, C. and Jarke, M. 1999. Query optimization for repository-based applications. In Selected Areas in Cryptography. Springer, 197–203.Google Scholar
Wang, T. 2006. Gauging ontologies and schemas by numbers. In Proc. of EON Workshop on Evaluation of Ontologies for the Web. ACM Press, USA.Google Scholar
You have
Access
- 10
- Cited by