Transforming Databases with Recursive Data Structures

My PhD. thesis was completed in 1995 as the final requirement for the PhD. program at the University of Pennsylvania Department of Computer and Information Science.

This thesis examines the problems of performing structural transformations on databases involving complex data-structures and object-identities, and proposes an approach to specifying and implementing such transformations.

It starts by looking at various applications of such database transformations, and at some of the more significant work in these areas. In particular it looks at work on transformations in the area of database integration, which was one of the major motivating areas for this work. It also looks at various notions of correctness that have been proposed for database transformations, and shows that the utility of such notions is limited by the dependence of transformations on certain implicit database constraints. It draws attention to the limitations of existing work on transformations, and argues that there is a need for a more general formalism for reasoning about database transformations and constraints.

It also argues that, in order to ensure that database transformations are well-defined and meaningful, it is necessary to understand the information capacity of the data-models being transformed. To this end if provides a thorough analysis of the information capacity of data-models supporting object identity, and shows that this is dependent on the operations supported by a query language for comparing object identities.

A declarative language, WOL, based on Horn-clause logic, is introduced for specifying database transformations and constraints. A method of implementing transformations specified in this language is also proposed, by manipulating their clauses into a normal form which can then be translated into an underlying database programming language.

Finally a number of optimizations and techniques necessary in order to build a practical implementation based on these proposals are presented, together with a discussion of the results of some of the trials that were carried out using a prototype of such a system.

See here for the thesis.

My PhD thesis proposal, entitled Types with Extents is also still available. See here for a summary and pointers.

Anthony Kosky (