Optimization Project home page.

---

Project Overview

Semantic query optimization uses problem-specific knowledge (e.g. integrity constraints) for transforming a query into an equivalent one (i.e., with the same answer set) that may be answered more efficiently.

The goal of this project is to develop algorithms and tools to perform semantic query optimization efficiently. The developed tool (called ODB-QOPTIMIZER) is based on two fundamental ingredients. The first one is the OCDL description logics proposed as a common formalism to express class descriptions, a relevant set of integrity constraints rules (IC rules) and queries as OCDL types. The second one are DLs (Description Logics) inference techniques exploited to evaluate the logical implications expressed by IC rules and thus to produce the semantic expansion of a given query. The optimizer tentatively applies all the possible transformations and delays the choice of beneficial transformation till the end. In addition, ODB-QOPTIMIZER is a ODMG compliant tool, both for the schema definition (ODL language) and for the query language (OQL).

Description

Let us briefly explain the main ingredients of our approach for semantic query optimization.

• OCDL: a description logics for database schema with integrity constraints

  OCDL (Object Constraints Description Language) is description logics languages in order to represent the semantics of complex object data models ( CODMs), proposed in the areas of deductive databases and object oriented databases. The main characteristics are: a distinction between values and objects with identity and, thus, between value types and class types (briefly called classes); type constructors, such as tuple, set and sequence recursively used to define complex objects, quantified path types and integrity constraints rules. Paths, which are essentially sequences of attributes, represent the central ingredient of OODB query languages to navigate through the aggregation hierarchies of classes and types of a schema. Quantified path are paths existentially and universally quantified. Integrity constraints (IC) rules are if then rules whose antecedent and consequent are OCDL virtual types (i.e. type descriptions expressing a set of sufficient and necessary conditions) allowing the declarative formulation of a relevant set of integrity constraints. For example, it is possible to express correlations between structural properties of the same class or sufficient conditions for populating subclasses of a given class.

• Query Optimization by DLs inference techniques

  A relevant set of queries can be expressed as virtual OCDL types; that is the ones referred to a target class and to the navigation through its composition hierarchy. Subsumption computation, incoherence detection and canonical form generation can be used to produce the semantic expansion of an OCDL query. It is a transformed query which incorporates any possible restriction which is not present in the original query but is logically implied by the query and by the overall schema (classes + value types + IC rules).