Title page for ETD etd-0415102-133008

Document Type dissertation

Author Name Koeller, Andreas

URN etd-0415102-133008

Title Integration of Heterogeneous Databases: Discovery of Meta-Information and Maintenance of Schema-Restructuring Views

Degree PhD

Department Computer Science

Advisors
Elke A Rundensteiner, PhD, Advisor
Carolina Ruiz, PhD, Committee Member
Nabil Hachem, PhD, Committee Member
Prof. Dr. rer. nat. habil. Gunter Saake, Committee Member

Keywords
schema restructuring
schema changes
meta-data discovery
data mining
data integration

Date of Presentation/Defense 2001-12-14

Availability unrestricted

Abstract
In today's networked world, information is widely distributed across many independent databases in heterogeneous formats. Integrating such information is a difficult task and has been adressed by several projects. However, previous integration solutions, such as the EVE-Project, have several shortcomings. Database contents and
structure change frequently, and users often have incomplete information about the data content and structure of the databases they
use. When information from several such insufficiently described sources is to be extracted and integrated, two problems have to be solved: How can we discover the structure and contents of and interrelationships among unknown databases, and how can we provide durable integration views over several such databases? In this
dissertation, we have developed solutions for those key problems in information integration.

The first part of the dissertation addresses the fact that knowledge about the interrelationships between databases is essential for any attempt at solving the information integration problem. We are
presenting an algorithm called FIND2 based on the clique-finding problem in graphs and k-uniform hypergraphs to discover redundancy
relationships between two relations. Furthermore, the algorithm is enhanced by heuristics that significantly reduce the search space when necessary. Extensive experimental studies on the algorithm both with and without heuristics illustrate its effectiveness on a variety of real-world data sets.

The second part of the dissertation addresses the durable view problem and presents the first algorithm for incremental view maintenance in schema-restructuring views. Such views are essential for the
integration of heterogeneous databases. They are typically defined in schema-restructuring query languages like SchemaSQL, which can
transform schema into data and vice versa, making traditional view maintenance based on differential queries impossible. Based on an
existing algebra for SchemaSQL, we present an update propagation algorithm that propagates updates along the query algebra tree and
prove its correctness. We also propose optimizations on our algorithm and present experimental results showing its benefits over view recomputation.

Files
koeller.pdf

Browse by Author | Browse by Department | Search all available ETDs

Questions? Email etd-questions@wpi.edu
Maintained by webmaster@wpi.edu

Document Type	dissertation
Author Name	Koeller, Andreas
URN	etd-0415102-133008
Title	Integration of Heterogeneous Databases: Discovery of Meta-Information and Maintenance of Schema-Restructuring Views
Degree	PhD
Department	Computer Science
Advisors	Elke A Rundensteiner, PhD, Advisor Carolina Ruiz, PhD, Committee Member Nabil Hachem, PhD, Committee Member Prof. Dr. rer. nat. habil. Gunter Saake, Committee Member
Keywords	schema restructuring schema changes meta-data discovery data mining data integration
Date of Presentation/Defense	2001-12-14
Availability	unrestricted
Abstract In today's networked world, information is widely distributed across many independent databases in heterogeneous formats. Integrating such information is a difficult task and has been adressed by several projects. However, previous integration solutions, such as the EVE-Project, have several shortcomings. Database contents and structure change frequently, and users often have incomplete information about the data content and structure of the databases they use. When information from several such insufficiently described sources is to be extracted and integrated, two problems have to be solved: How can we discover the structure and contents of and interrelationships among unknown databases, and how can we provide durable integration views over several such databases? In this dissertation, we have developed solutions for those key problems in information integration. The first part of the dissertation addresses the fact that knowledge about the interrelationships between databases is essential for any attempt at solving the information integration problem. We are presenting an algorithm called FIND2 based on the clique-finding problem in graphs and k-uniform hypergraphs to discover redundancy relationships between two relations. Furthermore, the algorithm is enhanced by heuristics that significantly reduce the search space when necessary. Extensive experimental studies on the algorithm both with and without heuristics illustrate its effectiveness on a variety of real-world data sets. The second part of the dissertation addresses the durable view problem and presents the first algorithm for incremental view maintenance in schema-restructuring views. Such views are essential for the integration of heterogeneous databases. They are typically defined in schema-restructuring query languages like SchemaSQL, which can transform schema into data and vice versa, making traditional view maintenance based on differential queries impossible. Based on an existing algebra for SchemaSQL, we present an update propagation algorithm that propagates updates along the query algebra tree and prove its correctness. We also propose optimizations on our algorithm and present experimental results showing its benefits over view recomputation.
Files	koeller.pdf