Browse Prior Art Database

Topological Approach For Testing Equivalence in Heterogeneous Relational Databases

IP.com Disclosure Number: IPCOM000128013D
Original Publication Date: 1985-Dec-31
Included in the Prior Art Database: 2005-Sep-14
Document File: 13 page(s) / 35K

Publishing Venue

Software Patent Institute

Related People

Ki H. Baik: AUTHOR [+4]

Abstract

A great deal of work has been directed towards the relational data model since Codd first introduced it (9). In this presentation, it will be assumed that the reader has examined the basic concepts of relational database theory [16,20,21]. The issue of equivalence between database schemes is another topic that ` has received a great deal of recent attention [2,6,7,13,14,15,17,18]. Researchers have looked at the problem of testing the equivalence of two database schemes defined over the same set of attributes. In the present work, a method for testing two heterogeneous relational database schemes for equivalence is given. To verify equivalence between two database schemes with. different attribute sets requires finding a dependency preserving mapping between the two attribute sets. To simplify the task of determining the mapping, a topology based on the functional dependencies is introduced. Based on the use of an optimal topology, two heterogeneous relational database schemes will be topologically equivalent if they are equivalent. In Section 2, the basic issues of topology are reviewed. Section 3 examines the selection process for an optimal topology. The section also presents an algorithm designed to test for topological equivalence and illustrates how the test can be incorporated into an algorithm to test database equivalence. - 2 -

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 14% of the total text.

Page 1 of 13

THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.

Topological Approach For Testing Equivalence in Heterogeneous Relational Databases

Ki H. Baik and L.L. Miller

September 1985 r TR #85-26

1. Introduction

A great deal of work has been directed towards the relational data model since Codd first introduced it (9). In this presentation, it will be assumed that the reader has examined the basic concepts of relational database theory [16,20,21].

The issue of equivalence between database schemes is another topic that

` has received a great deal of recent attention [2,6,7,13,14,15,17,18]. Researchers have looked at the problem of testing the equivalence of two database schemes defined over the same set of attributes.

In the present work, a method for testing two heterogeneous relational database schemes for equivalence is given. To verify equivalence between two database schemes with. different attribute sets requires finding a dependency preserving mapping between the two attribute sets. To simplify the task of determining the mapping, a topology based on the functional dependencies is introduced. Based on the use of an optimal topology, two heterogeneous relational database schemes will be topologically equivalent if they are equivalent.

In Section 2, the basic issues of topology are reviewed. Section 3 examines the selection process for an optimal topology. The section also presents an algorithm designed to test for topological equivalence and illustrates how the test can be incorporated into an algorithm to test database equivalence. - 2 -

Note that from the definitions, there are potentially several bases and subbases for a topology. The smallest base in terms of size is called a minimal base and the smallest subbase is called a minimal subbase.

Example 1: consider a set

(Equation Omitted)

and the sets

(Equation Omitted)

The topology T generated is

(Equation Omitted)

Iowa State University Page 1 Dec 31, 1985

Page 2 of 13

Topological Approach For Testing Equivalence in Heterogeneous Relational Databases

The example illustrates the fact that X is always a member of BASE[T], since the intersection of an empty family of sets is X. Similarly, (6 is always in T due to the fact that the union of an empty family of sets is

Let Td denote the power set of X. Observe that Td satisfies the axioms for a topology on X. Td is called the discrete topology on X and the topology {0,X} is known as the indiscrete topology on X. Let T1 and T2 be two topologies on the set X. Suppose T1 G T2, then T1 is said to be coarser than T2 or T2 is finer than T1. Observe that the collection of all topologies on X is partially ordered by the inclusion property. The discrete topology is the finest topology and the indiscrete topology is the coarsest topology. The bound on the size of a topology is given as 2 < ITI < 2n, where n = IXI. Let

(Equation Omitted)

be topological spaces. A mapping

(Equation Omitted)

is continuous if and only if P E T2 implies

(E...