Return to search

CGU: A common graph utility for DL Reasoning and Conjunctive Query Optimization

We consider the overlap between reasoning involved in <em>conjunctive query optimization</em> (CQO) and in tableaux-based approaches to reasoning about subsumption in <em>description logics</em> (DLs). In both cases, an underlying graph is created, searched and modified. This process is determined by a given <em>query</em> and <em>database schema</em> in the first case and by a given <em>description</em> and <em>terminology</em> in the second. The opportunities for overlap derive from an abundance of reductions of various schema languages to terminologies for common DL dialects, and from the fact that descriptions can in turn be viewed as queries that compute a single column. <br /><br /> Our main contributions are as follows. We present the design and implementation of a common graph utility that integrates the requirements for both CQO and DL reasoning. We then verify this model by also presenting the design and implementation for two drivers, one that implements a query optimizer for a conjunctive query language extended with descriptions, and one that implements a complete DL reasoner for a feature based DL dialect.

Identiferoai:union.ndltd.org:WATERLOO/oai:uwspace.uwaterloo.ca:10012/1101
Date January 2005
CreatorsPalacios Villa, Jesus Alejandro
PublisherUniversity of Waterloo
Source SetsUniversity of Waterloo Electronic Theses Repository
LanguageEnglish
Detected LanguageEnglish
TypeThesis or Dissertation
Formatapplication/pdf, 717484 bytes, application/pdf
RightsCopyright: 2005, Palacios Villa, Jesus Alejandro. All rights reserved.

Page generated in 0.0018 seconds