Login

Publications  •  Project Statistics

Glossary  •  Schools  •  Disciplines
People Search: 
   
Title/Abstract Search: 

Dissertation Information for Catharine Marie Wyss

NAME:
- Catharine Marie Wyss

DEGREE:
- Ph.D.

DISCIPLINE:
- Computer Science

SCHOOL:
- Indiana University (USA) (2002)

ADVISORS:
- None

COMMITTEE MEMBERS:
- None

MPACT Status: Incomplete - Not_Inspected

Title: Relational interoperability

Abstract: "This thesis extends the relational query languages to provide natural and complete incorporation of relational metadata into database queries in order to support relational interoperability.

The most serious aspect of the challenge of relational interoperability amounts to dealing with several databases containing comparable information in different representations. Although the underlying model is the same, the actual structures employed may be dramatically different. In particular, what is data according to one source may be metadata (structural elements) according to another. Support for relational interoperability therefore involves the ability to query and interchange metadata along with ordinary relational data. Toward this end, we present a coherent, formal framework for supporting relational interoperability consisting of an extended SQL language, FISQL, and an equivalent relational algebra, FIRA. We provide a full EBNF for FISQL and a declarative, compositional semantics.

A strength of our framework is that FISQL inherits the most desirable properties of SQL, including a modest complexity (LOGSPACE), sufficient expressiveness, natural incorporation into relational systems, and support for nested queries. Beyond SQL, FISQL provides the ability to write queries that are independent of any particular, fixed relational schema, as well as the ability to promote data to any level of the metadata hierarchy and demote metadata to data arbitrarily.

The central result of this thesis is that FISQL is equivalent to FIRA. FIRA is an extended relational algebra and contains a sub-algebra that is isomorphic to the canonical relational algebra. Previous frameworks for relational interoperability have lacked such an algebra. A unique contribution of our work is to provide methods for automated query optimization using FIRA in conjunction with well-known, sound optimization techniques arising within the canonical relational model. This entails that, for the first time, we can support real-time, peer-to-peer interoperability within a large federation of relational databases.

In addition, the formal nature of our framework has revealed at least one reason why unrestricted data-metadata integration is difficult: this is encapsulated in our proof that Optimal Tuple Merge is NP-Complete. Although the problem of merging tuples arises naturally when promoting data to metadata, we have also identified a large class of relations for which Optimal Tuple Merge is easily solved. Thus, we are able to meet the user's expectations for relational interoperability in a broad range of practical cases."

MPACT Scores for Catharine Marie Wyss

A = 0
C = 1
A+C = 1
T = 0
G = 0
W = 0
TD = 0
TA = 0
calculated 2008-01-31 06:33:19

Advisors and Advisees Graph