  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 OWL 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 OWL ontologies, and shows that the techniques are accurate and
improve query performance. To appear in Theory and Practice of Logic
Programming (TPLP).
