SCHEMA TRANSFORMATION PROCESSORS
FOR FEDERATED OBJECTBASES
Markus Tresch Marc H. Scholl
Department of Computer Science, Databases and Information Systems
University of Ulm, D-W 7900 Ulm, Germany
{tresch,scholl}Oinformatik.uni-ulm.de
ABSTRACT
In contrast to three schema levels in centralized object-
bases, a reference architecture for federated objectbase sys-
tems proposes five levels of schemata. This paper investi-
gates the fundamental mechanisms to be provided by an
object model to realize the processors transforming be-
tween these levels, namely schema ezlension, s&emu fil-
tering,
and
schema composition.
It is shown, how com-
position and extension are used for stepwise bottom-up
integration of existing objectbases into a federation; and
how extension and filtering support authorization on dif-
ferent levels in a federation. A powerful View definition
mechanism and the possibility to define subschemata (i.e.,
parts of a schema) are the key mechanisms used in these
processes.
1
INTRODUCTION
Federated objectbase (FOB) systems as a collection of co-
operating but autonomous local objectbases (LOBS) are
getting increasing attention [8].
To
clarify the various is-
sues, a first reference architecture for federated database
systems was presented by Sheth and Larson [16]. While
the ANSI/SPARC three-level schema architecture was ad-
equate for centralized objectbases, they introduced five
schema levels for FOBS: (i) the local
schema as
the concep-
tual schema of a LOB, expressed in the native data model
of each LOB; (ii) th
e component schema
as the translation
of the local schema into a canonical data model, that is, a
model common to the federation; (iii) the
export schema
as a subset of the component schema, holding the part
that is made available to the federation and its users; (iv)
the
federated schema
as the integration of multiple export
schemata, forming the global conceptual schema; (v) the
external schema
as a special view of the federated schema,
customized for a class of federation users / applications.
A close look at this five-level reference architecture
leads to the following observations:
1. Federated
schemata are huge.
A federated schema,
as the global conceptual schema of the FOB, may contain
thousands of types and classes. Moreover, due to semantic
heterogeneity, a large number of structural conflicts may
have to be solved. Thus, static integration of many LOB
schemata into one federated schema at one shot is not ap-
propriate, or even not feasible.
2.
A view
(subschema) mechanism is needed. So
far, no widely accepted notion of views and subschemata
in object-oriented database systems exists. However, this
is essential for support of customization and access control
on LOB as well as on FOB level. Within LOBS, views (sub-
schemata) are needed to specify the exported part of the
objectbase; within FOBS they are used to define external
schemata of the federation.
3. Enforcing fixed schema levels is
to restrictive.
FOBS are supposed to make existing data repositories dy-
namically work together. Requiring five specific schema
levels maybe too static; in fact, it might even be con-
sidered to violate the overall idea. Thus, not predefined
schema levels, but types of schema transformation proces-
sors should be the main concern.
4. Local objectbases are populated. An FOB is basi-
cally developed in a bottom-up process by integrating ex-
isting LOBS. Each of these LOBS supposedly comes with
already stored objects (type/class instances). Thus, to-
gether with schema integration, construction of the FOB
must also consider the problem of unifying objects from
different LOBS that represent the same real world entity.
This article identifies the fundamental mechanisms that
transform between the different levels of schemata in an
FOB, while at the same time taking into account the
above observations. We thereby restrict our considera-
tions to LOBS with homogeneous data models. That is,
we treat the problem of data model transformation as a
separate issue. As a representative data model, we use
the object-oriented model COCOON, presented together
with its algebra in Section 2. However, investigations are
not limited to that model, but can similarly be applied
to most other object-oriented models/systems. Section 3
introduces three basic schema transformation processors:
schema extension, schema
filtering, and
schema composi-
tion.
In Section 4, we describe how to use schema composi-
tion together with schema extension for the purpose of in-
tegrating multiple LOBS into an FOB. Section 5 shows how
to manage authorization and access control in FOBS using
37
schema extension combined with filtering. A comparison
to other related work is made in Section 6. Finally, Sec-
tion 7 shows, how the basic schema transformation proces-
sors fit into Sheth/Larson’s reference architecture for fed-
erated objectbases, and concludes with an outlook on open
issues.
2 AN OBJECT MODEL AND
ALGEBRA
We briefly review the key concepts of the object model
COCOON and its algebra [13], used throughout this pa-
per. The COCOON object-model is an object-function
model with the basic constituents
objects, functions, types,
classes,
and views:
Objects
are instances of abstract object types (AOTs),
specified by their interface operations. In contrast,
Data
are instances of concrete types (e.g., numbers, strings) or
constructed types (e.g., tuple or set).
Functions
are the generalized abstraction of attributes
(stored or computed), relationships between objects, and
update methods (with side-effects). They are described
by their name and signature, i.e. domain and range.type.
Functions can be single- or set-valued. The implemen-
tation is given separately, in the object implementation
language (OIL), whi6h is not described here any further.
Types
describe the common interface to all of its in-
stances. So, a type t is defined by a set, of applicable
functions
functs(t).
Th e subtype (is-a) relationship, which
is
used
for type-checking, corresponds to subset relation-
ship of function sets, such that type tz is subtype of tl iff
functs(ta)
_>
functs(tl).
The root of the type lattice is the
predefined type
object.
The language is strongly typed, in
the sense that it supports full static type checking. Types
can be named. However, this is optional because new types
can arise dynamically as any set of functions.
Classes are strictly distinguished from types [4]. A
class c is a typed collection of objects. It has an associated
member type
mtype(c)
and an actual extension
extent(c),
i.e. the set of objects in the class. We define the extent of
a class to include the members of all its subclasses, such
that objects can be member of multiple classes at the same
time. The subclass relationship is defined on the subset
relationship of class extension and subtype relationship.
Hence, c2 is a subclass of cl iff
extent(c2) c extent(q) A
functs(mtype(c2)) > functs(mtype(q)). The
top class of
this hierarchy is the
class Objects.
Views are virtual (derived) classes, that is, classes
whose extent and member type are computed by a query
expression. We discuss views in more detail in Section 3.1
below.
An
objectbase schema is a representation of the struc-
ture (syntax), semantics, and constraints on the use of an
objectbase in the object model. In the COCOON model,
this is
given
as follows by classes, views, types, and func-
tions:
Definition 1.
(Database Schema) A database schema is
a four-tuple S = < C,
V, T, F
>, with
0 C a set of given classes;
l
V
a set
of views
defined on classes C;
l
T = UCEC mtype(c) ” U”E” mtype(v)
the set of
member types of classes C and views
V;
l
F = UtETfuncts(t)
the set of functions of types
T.
Example 1:
As a running example throughout this pa-
per, we use the sample scenario shown in Figure 1. It
illustrates a situation in a company, using two indepen-
dent COCOON objectbases:
SalesDB
in the sales depart-
ment, storing information about articles and customers;
and
ProdDB
in the production department, with data on
raw materials and their suppliers.
define database SalesDB as
define type article isa object =
matn:
integer ,
boughtby: set of customer inv bought ;
define type screw isa article =: thread: string ,
define type customer isa object =
name, addr: string ,
bought: set
of
article inv boughtby ;
define class Articles: article ;
define class Screws:
screw
some Articles;
define class Customers: customer ;
end ;
define database ProdDB
as
define type material isa object = mno: integer ,
weight: kilo ;
supplby: supplier inv
supplies
;
define type supplier isa object =
name, street, city: string ,
supplies:
set
of materials inv supplby ;
define class
Materials:
material ;
define class Suppliers: supplier ;
end ;
The schemata of the two
databases
SalesDB
and
ProdDB
are given as:
SSalesDB = <
SProdDB = <
{Articles, Screws, Customers}, {},
{article, screw, customer},
{ano,
price,
matn, boughtby, thread,
name, cstreet, addr, bought} >
{Materials, Suppliers}, {},
{material, supplier),
{mno, weight, supplby, name, street,
city, supplies} >
38
SalesDB
bought
ProdDB
Figure I: Local objectbases
SalesDB and ProdDB
We use a
set-oriented query language
similar to (nested)
relational algebra, where the inputs and outputs of the
op-
erations are sets of objects. Hence, query operators can be
applied to extents of classes, set-valued function results,
and query results. The algebra has an object-preserving
semantics, in the sense that queries return (some of) the
input objects. This semantics for queries allows the ap-
plication of methods and update operations to results of a
query, since these contain base objects. As query operators
we provide selection of objects, projection, extension, and
the set operations for union, intersection, and difference.
3 BASIC SCHEMA TRANS-
FORMATION PROCESSORS
In this section we define and analyze three basic schema
transformation processors for federated objectbases: (i)
schetna eztension to add new derivable information per-
sistently to a schema, (ii) jili ering to hide schema informa-
tion from users, and (iii) composidion to combine several
schemata together.
3.1
Schema Extension
It is widely accepted for relational systems that a pri-
mary step towards extensibility and flexibility of database
schemata is the powerful mechanism of defining vieurs (per-
sistent queries). In the COCOON model, views are de-
fined as virtual classes, whose extent and type is derived
by a query based on other classes [12]. The main differ-
ence to other object-oriented view approaches is that we
use the query language (object algebra) and do not intro-
duce special-purpose syntactic constructs for view defini-
39
tion. Hence, views are declared as
define view v as e ;
with e an (algebraic) query expression of arbitrary com-
plexity. Another important difference is that views are
positioned in the type and class hierarchies according
to
their computed type and extent.
Notice, that views can also be defined over other views
or by composite queries. Below, we describe what the
member type and the extent is, and how these are po-
sitioned in the type and class hierarchies.
Selection views
( define view v as selectb](e) ).
The
extent of the view v is a subset of the base class’ members,
namely those satisfying the predicate p. The member type
remains unchanged, such that there are now two classes,
v and c, of that type. Consequently, the view class 21 is
positioned as subclass of the base class c.
Projection
views (
define
view v as project[f, . . .](e)
). The member type of view v is a supertype of the origi-
na1 one, since less functions are defined on it, namely those
listed in the projection. However, projection does not ma-
nipulate the extent, such that the extent of v is the same as
that of e. The view is therefore positioned as a superclass
v is a superclass of c.
Extend views ( define view v as
extendIf :=
ezpr, . . .](e) ). While projection eliminates functions, ex-
tend defines new derived ones f, by any legal arithmetic,
boolean, or set-expression
expr. So,
the type of view v is a
subtype of the base class’ type, since it has more functions
(all the old functions
plus
the new ones are defined). Like
with projection, the extent is unchanged again. The view
v is therefore a subclass of c,.
Set-operaior views ( define view v
as
e uniou 1
in-
tersect
1 difference
e; ). As the extent of classes are sets
of objects, we can perform skt operations as usual. These
views change extents as well as member types. However,
in a polymorphic type system, we need no restrictions on
operand types of set operations (ultimately, they are all
instances of type
object).
A union view creates a com-
mon superclass of its bases classes, where the extent is the
union of the base class’ objects, and the member type is
the lowest common
supertype (intersection of base class
functions) of the input types. An intersection view is com-
mon subclass, with the intersection of the input objects
and the greatest common supertype (union of base class
functions) as member type. Finally, difference views are
subclasses of their base classes.
Based on the abstraction of derived classes as views,
schema extension is now defined as the processor that en-
hances a given schema with derived information.
Definitiou 2.
(Schema Extension) Let S = <
C,
V,T, F
> be a database schema. Furthermore, let
V’S
be a set of views defined on C and
V.
The extension of
S by
Vs
is a schema S’ = < C’,
V’,T’, F’
> with C’ = C
and
V’=
VUVs.
Recall from Definition 2, that types (2”) and functions
(F’) are computed from C’,
V’.
Related to federated sys-
tems, schema extension is used on two different levels. In
LOBS to customize the component schema before it par-
ticipates the federation, and in FOBS to create external
schemata of the global federated system.
Example 2: The following DDL statements define a
schema
SalesDB-1
as an extension of
SalesDB.
The im-
port clause makes the base schema available, such that
additional views can be defined.
define schema
SalesDB-1
as
import
SalesDB ;
define view
PuLlArticles
as
project [
ano, matn, boughtby ] ( Articles ) ;
define view
Articles US$
as
extend
[ price$:= price *0.657 ] ( Articles ) ;
define view UselessCuslomers as
select
[ bought = {} ] ( Customers ) ;
exld ;
Figure 2: Schema
SalesDB-1
as the extension
of SalesDB
with view classes.
The extended schema
SalesDB-1
is illustrated in Fig-
ure 2. Notice, how views are positioned in the class hier-
archy. Whereas selection and extend views are subclasses
of their base class, the projection view is a superclass.
S
SalesDB- 1 =
<{Articles, Screws, Customers},
{PublArticles, ArticlesUS$, UselessCustomers},
{article, screw, customer,
[ano, matn, boughtby], [ ano, matn, price, price$]},
{ ano, price, price$, matn, boughtby, thread,
name, addr, bought} > .
Remember that types are sufficiently specified by
their applicable set of functions and need not be named.
E.g., the projection and the extension view produce
new (unnamed) types. For unnamed types we alterna-
tively enumerate its function sets
[ano, matn, boughtby]
and
[ano, matn,price,price$]
in the schema description.
3.2 Schema Filtering
The opposite processor of adding derived information to
a schema is filtering, that is, excluding parts of a given
schema (e.g., classes and views). After extending a schema
with derived information, it is desirable to identify a subset
of classes and views in order to build a subschema. Only
the selected classes and views of a subschema are then
exported to foreign services (such ~5 users, applications,
or other systems).
Definition 3. (Subschema) Let
S = < C, V,T,F >
be a schema. Then a subschema of S is a schema S’ = <
C’,
V’, T’, F’
> with C’ c C and
V’ G V.
Schema filtering processors are used in LOBS together
with schema extension to define a customized (sub-)schema
that does not contain all component classes and views of
the LOB. In a FOB, subschemata are similarly used as
global external schemata. Below, we give an example on
how to use subschemata to hide information from a users.
Example 3: To define a subschema without pricing in-
formation, we first extend
SalesDB
with view
PublArticles
projecting out the
price
function from the class
Articles.
Then the export clause is used to make visible just the
class
Customers,
the view
PublArticles,
and nothing else.
define schema
SalesDB-2
as
import
SalesDB ;
define view
PubIArticIes
as
project
f ano, matn, boughtby ] ( Articles ) ;
export
Customers, PublArticles ;
end ;
The resulting subschema
SalesDB-2
is illustrated by the
dotted area in Figure 3.a below:
SSalesDB- 2 =
<{Customers}, {PublArticles},
{customer, [ano, matn, boughtby]},
{ano, matn, boughtby, name, addr, bought} > .
The major restriction to be imposed on subschemata
is (transitive)
closure
of types. This attacks the problem
that there must not be a function in a subschema that
“leads out of it”. More formally, the range type of each
function of a subschema has to be part of the subschema
itself. “Open schemata” must be omitted, since programs
running with them may result in run-time type errors. It
is quite intuitive, that an application cannot handle ob-
jects whose types are not described in the schema. This
restriction leads to the following revised definition:
Definition 4. (Closed Subschema) Let S = <
C,
V, T, F
> be a schema. Then a closed subschema of
S is a schema S’ = < C’,
V’, T’, F’
> with C’ C C and
V’
E
V,
such that Vf E
F’
with
range(f)
5 object :
range(f) E T’.
40
For closure, we consider only object-valued functions,
that is, functions returning an instance of an abstract ob-
ject type. We assume that primitive (value) types (such
as integer, boolean, and string) are by definition part of
any schema, that is, functions with such range types do
not lead out of the schema, even if we did not explicitly
include their range.
price
Alticles
R
Screws thread
0)
e thread
(4
Figure 3: (a) Not closed subschema SalesDB-2 and (b)
closed subschema SalesDB-3.
Notice that the subschema of Figure 3.a is NOT closed.
This can easily be seen, because the function bought leads
out of the dotted area. The application of function
bought(c) to a given customer c is a valid expression ac-
cording to open subschema SalesDB-2. The result is a set
of articles, though the type article is not part of the schema
(only a supertype of it, namely [ano, matn, boughtby]).
To make ‘the schema closed, the transitive closure of all
functions’ range types must be built (see also [ll]), which
results in the following closed version of SalesDB-6:
SSalesDB-2. =
<{Customers}, {PublArticles},
{customer, [ano, matn, boughtby], article},
{ ano, matn, boughtby, name, addr, bought, price} > .
The schema is now closed again. However, the price func-
tion was included, which is exactly what we wanted to
avoid. The way out from the above dilemma is an en-
hanced projection operator that allows to redirect function
range types. The redirecting projection allows to change
the range type of a projected function in the projection
list:
project [ Jft, . . . ] ( e ); with t 2 range(f).
Redirection must be limited to supertypes in order to stay
within the type checking possibilities of a polymorphic type
system.
Example 4: The revised attempt to find a closed sub-
schema without pricing information is to define two redi-
recting projection views as follows:
define schema SalesDB-3 as
import SalesDB ;
define view PubIArticles as
project [ ano, matn, boughtby::PublCustomers ]
( Articles ) ;
define view PublCustomers as
project [ name, addr, bought::PublArticles]
( Customers ) ;
export PublArticles, PublCustomers;
end ;
In the final subschema SaIesDB-3, just these two views
are made visible. Figure 3-b shows that SalesDB-3 is now
closed and information about prices are completely hidden.
SSalesDB-3 =
<{}, {PublArticles, PublArticles},
{[ano, matn, boughtby :: PublCustomers],
[name, addr, bought :: PubIArticles]},
{ano, matn, boughtby :: PublCustomers,
name, addr, bought :: PublArticles} > .
An
important observation about closure of subschemata
is that there is no restriction on the classes, only on
types. Obviously the sole purpose of schema filtering is
to hide some object collections (i.e., classes) from the ex-
port schema, so there should not be a need for inclusion
of classes (or views) into an export schema because of clo-
sure constraints. Patticularly, we do not need to include
the base class(es) of a view into the subschema when in-
cluding the view.
3.3
Schema Composition
Both schema transformations presented so far operate on
one single schema. The next processor, called schema com-
position, is the first step towards interoperability of mul-
tiple objectbase systems.
41
It is the elementary process that combines schemata
of multiple LOBS into one
composed schema.
This is
the foundation for establishing a federated objectbase
sy5
tern. Schema composition places only minimal require-
ments on the degree of integration between participating
objectbases. In fact, it basically just imports the names of
all schema elements (classes, views, types, and functions)
from LOBS and makes them globally available [14].
Example
5: Assume we want to create a FOB
FedDB
consisting of the LOBS
SalesDB
and
ProdDB
from Ex-
ample 1. The very elementary step is to compose the
schemata of the participating systems. Figure 4 graphi-
cally illustrates how schemata of
SalesDB
and
ProdDB
are
put side-by-side by the following import clauses.
define schema FedDB as
import SalesDB ;
import ProdDB ;
end ;
Figure 4: Composition of local schemata
SalesDB
and
ProdDB
into
FedDB
More precisely, composition of local objectbases LOB;
into a federated system
FOB
combines the class and type
systems of the local objectbases. First, the basic data types
(integer, string, . ..) of the different systems are unified.
Second, the class and type hierarchies of the local object-
bases are put together on the schema level AND on the
meta-schema level in the following (so far trivial) way:l
Schema Level:
A global schema is created with a new
top type
object@FOB,
a new bottom type
bottom@FOB,
and a new global top class
Objects@FOB.
The global type hierarchy is established, where all top
types of the local objectbases
(object@LOB;)
are made di-
rect subtypes of the new global top element
object@FOB.
The new bottom type
bottom@FOB
is made common sub-
type of all local bottom types. No further subtype rela-
tionships are established.
‘ln the sequel, we use the naming convention that schema com-
ponents are suffixed by W’ and the name of the local schema.
For example,
class
Articles in SalesDB has as globally unique name
“ArticleaOSaleaDB”.
Similar, a global subclass hierarchy is composed, with
the new top element
Objects@FOB
as common superclass
to all local top classes
Objects@LOBi
(see Figure 4).
Meta-Schema Level:
A global meta-schema is created
as well. This is the meta schema of the
FOB.
The meta-
schema of each
LOBi
contains three meta types
class, type,
functions
and three meta classes
Classes, Types, Functions,
respectively (a detailed discussion of the COCOON meta-
schema is contained in [20]).
A global meta-schema is created with new types
class@FOB, type@FOB,
and
function@FOB, as well as
three new meta classes
Classes@FOB, Type&FOB, and
Function&FOB.
The
FOB
meta-schema has therefore ex-
actly the same structure as that of each
LOBi.
Then,
the local meta classes and meta types are made sub-
class/subtype of their global counterparts.
Furthermore, meta functions are unified during the
composition process, e.g., in each
LOBi
there is a meta
function
superAypes(t)@LOBi
finding all supertypes of a
given type t. These functions are all automatically unified
over all objectbases.
Definition 5.
(Schema Composition) Let S1 = <
G,K.,Tl,Fl >,..., S,, = < C,,,
V,, T,, F,,
> be database
schemata. Then the composition of ,!!I, . . . , S, is a schema
S’ = < C’,V’,T’,F’
> with C’ = COUCI U...UC,,
and
V’ = VI
U
. . .
U
V,, where Co = { Objectso, Classeso,
Typeso, Functions0
} is the set of federated meta classes.
Schema composition is not yet real “objectbase integra-
tion”. In particular, no instance of
object@FOB
is instance
of
more
than one component type
object@LOBi.
Further-
more, the extent of
Object&FOB
is partitioned into
dis-
joint
subsets
Objects@LOBi.
As a consequence, no two
objects in
Object&FOB
can be the same (identical), un-
less they originate from the same
LOB;
and are identical
in
LOBi.
4 INTEGRATION OF OBJECT-
BASES
Real integration of instances and schemata is performed
quite easily by applying schema extension processors to
formerly composed
LOBi
schemata.
Since objectbase integration is not the main topic of
this paper, but should just
be
discussed as an application
of schema transformation processors, we refer for more for-
mal details on the mechanism (i.e., same-functions, global
identity, solving structural and semantic conflicts) to [14].
We recall here some of the results, as far as they are nec-
essary to understand how extension, filtering, and compo-
sition processors work on FOBS.
42
4.1 Unifying Objects
Since LOBS have been used independently of each other,
one real world (entity) object may be represented by differ-
ent database (proxy) objects in different LOBS. The fun-
damental assumption of object-oriented models, namely
that one real world object is represented by exactly one
database object, is therefore no longer true in FOBS [9].
We therefore need an additional notion: we say that two
local objects are ihe same, iff they represent the same real
world (entity) object.
Same objects are identified in FOBS by extending the
composed schema using extend views to define so called
same-functions. Formally, we require that for any two
types from different LOBS (Ti from LOBi and Sj from
LOBj), the instances of which shall be unified, we are
giving a query expression that determines, for a given Ti-
object, what the corresponding Sj-object is (if any), and
vice versa. This query expression is used to define a derived
function sameT,,Sj from Ti to Sj and its inverse, Samesj ,T;.
Obviously, these query expressions are application depen-
dent and can, in general, not be derived automatically.
To state that instances of type customer of SalesDB
are identical with instances of type supplier of ProdDB, if
they have identical names, for example, we have to defined
the following same-functions:
extend [ samecu,tomer,supplier :=
pick(select[name(‘c)=name(s,)](s:Suppliers)) ]
( c:Customers ) ;
extend [ Sam~upplier,customer :=
pick(select[name(‘s,l=name(cll(c.Cus~omers)) ]
( s:Suppliers ) ;
Notice, that the
pick
operator does a set collapse, that
is, it takes a single object out of a singleton set. This is
valid here, since we assume that each object in one ob-
jectbase corresponds to at least one object in the other
objectbase.
4.2 Schema Integration
After unifying proxy objects in different LOBS, we now
focus on schema integration, that is to find out, what the
common parts in the local schemata are, and to define a
correspondence among them.
In Subsection 3.3, we said that schema composition also
constructs a global meta schema. To define correspon-
dences between functions from different LOBS, we make
use of the fact, that every function is represented by a
meta object. Thus, integrating functions from LOBi and
LOBj is now straightforward: we unify the objects that
represent the functions in the meta-schema by defining
a same-function from meta type function@LOBi to meta
type function@LOBj.
To unify for example the functions name@SalesDB and
name@ProdDB, the following same-function is defined on
the meta schema of FOB:
extend [
samy
unctionQSalesDB,~nctionOProdDB :=
pick(select [name(f) = ‘name’
A name(g) = ‘name’ ]
( g:Functions@SolesDB ))
] ( fiFunctions@ProdDB ) ;
In contrast to most other schema integration approach
that emphasis on solving semantic and structural conflicts
among different systems [3, 171, we concentrate here on
reducing schema integration to unifying meta objects.
4.3 Objectbase Integration Method
We have now defined all prerequisites for tight objectbase
integration: we showed how to find “same” objects over
muItiple systems and discussed schema integration as uni-
fication of meta-objects. As a consequence, we can now
come up with a methodology for stepwise integration of
populated objectbase systems that uses schema composi-
tion together with extension:
Step 1. Use schema composition to put LOB schemata
side-by-side and to make types and classes known to each
other.
Step 2. Use schema extension to add extend views with
same-functions to identify proxy objects from different
LOBS that represent the same entity object from the real
world. Use this mechanism also to integrate correspond-
ing parts of the LOB schemata into an uniform schema
element in the FOB, by unifying meta objects represent-
ing functions from different LOBS.
Step 3. Use schema extension again to add views that
span over several objectbases. They now respect same ob-
jects from different
LOBS
and same properties from differ-
ent
LOB
types.
Example 6:
Reconsider the schema FedDB. Following
to the above method, we first compose the local schemata
by importing SalesDB and ProdDB. Then, we extend the
classes Customers and Suppliers with same-functions. Fi-
nally, the meta class Functions@SalesDB is extended to
integrate name@SalesDB and name@ProdDB properties.
define schema
FedDB
as
import
SalesDB ;
import
ProdDB ;
define view
Customers’@SalesDB
as
extend .,.
/* see Subsection
4.1 */ ;
define view
Suppliers’ @ProdDB
as
extend .,.
/” see Subsection
4.1 */ ;
define view
Functions’@SalesDB
as
extend . . .
/* see Subsection
4.2 */ ;
define view
Persons
as
Customers’@SalesDB
union
Suppliers’@ProdDB ;
end ;
Now, we are ready to define views that span mul-
tiple objectbases, e.g., a view Persons as the union
over the extended classes
Customers’@SalesDB
and
Supplierd @ProdDB.
One point of interest is the extent and the type of
the
union view. The extent is defined to be the union
of the objects of the base classes. However, if there
would be a customer object and a supplier object, hav-
ing equal names, they are defined through the same-
function to represent one and the same real world ob-
ject, and will therefore appear only once in the union
view. The type of a union view is defined as intersec-
tion of the functions of the base classes. Thus, since
the type of
Customer’
is
[name, addr, bought, same,,,]
and
of
Suppliers
is
[name, street, city, supplies, same,,,],
and
name@SalesDB
and
name@ProdDB
functions are defined
to be the same, the type of the view is
[name].
5
ACCESS CONTROL AND
AUTHORIZATION
FOBS are supposed to bring together several component
systems. Federation users will therefore have possible ac-
cess to large data repositories. Consequently, access con-
trol and authorization is a major problem in the design of
federated systems. In this section, we discuss the possi-
bilities there are to permit or deny access to objects in a
federation, using schema extension and filtering processors.
5.1 Authorization Possibilities
So far, we introduced two mechanisms of hiding specific
information from users:
views
and
subschemata.
Views,
as virtual classes, operate on collections of objects. The
possibilities of a query language are available to restrict
either the set of visible objects, or the applicable functions.
Subschemata, as a collection of classes and views, operate
on whole schemata. They are used to grant access to a
specific user for a defined subset of a given schema.
Selection views are used to hide some of the objects
in a class. The hidden objects must be describable by a
predicate using information of the database. We can for
example hide expensive screws from users of
SalesDB:
define view
CheapScrews
as
select [ price < 10 ] (
Screws );
A first idea of how to use projection views in order to
hide properties of classes was given in Example 3. More-
over, since functions are abstractions of stored properties
as well as of methods, access can be restricted to read,
write, or update. Consider in the same example the class
Articles
with an additional method
get-price.
Projecting
out the property
price
while keeping
get-price,
has the ef-
fect of setting a read-only privilege.
Extend views are thought to keep the result of a query
as a new property of objects. As we have seen also in Sec-
tion 4, this is a very powerful mechanism. For authoriza-
tion purposes, extend views are adequate to show a new
derived property. Assume, users of the
Materials
class are
not allowed to see the supplier, but need to know the city
where the material is supplied from.
define view
Materials’
as project [
mno,
weight, ciiy ]
(
extend
[ scityr= city(suppZby(m)) ]
(m:Malerials ) ) ;
Union views make physical distribution transparent.
Suppose a union of two classes from different LOBS. If
only the union view is visible, a user does not (need to)
know in which LOB the objects are physically stored.
Schema extension together with filtering processors are
well suited as the basic mechanisms for flexible control of
object access in FOBS. In fact, due to object identity,
we do not have the problem of view updatability in our
model. Furthermore, abstract object types, object encap-
sulation, and type-specific methods enhance to possibilities
of authorization using view classes, compared to relational
systems for example. We thereafter propose the following
two-step authorization method:
Step 1. Use schema extension to define a view class on
those
classes where
you want to hide some information.
Step 2. Use schema filtering to define a subschema, in-
cluding your defined views, while filtering out their base
classes.
Notice, that filtering out the base class of a view does
not restrict updatability. In the example above, we can
create a new screw object in the view
CheapScrews
at any
time. The update will be propagated to the base class
Screws,
even if it is not part of the subschema. The.only
side-effect is, that if the newly added object was not a
cheap one, it is afterwards not any more visible in the
view. Nevertheless, the object is available as an article of
course.
5.2 Levels of Access Control
In FOBS, we use schema extension and filtering proces-
sors mainly on two different levels: (i) related to LOBS
to specify export schemata and therefore to control access
to a component system; (ii) related to FOBS to specify
global external schemata and therefore to control access
to the global federated system. Negotiations between the
component DBAs and the federation DBA is necessary to
agree who has the control access on which objects.
Example 7: Consider the following scenario: the two
LOBS given in Example 1 should be merged into a feder-
ated system, such that there will be two new customized
databases, a
PersonDB
holding all information about cus-
tomers and suppliers, and a
ConstructionDB
with all data
on articles and materials. To do this, there are mainly two
possible alternatives to combine the LOBS
SalesDB
and
ProdDB,
both of which come to the same result.
44
PenonDB CanstwctkmDB PwsonDB ConmctionDB
Global00 Customer00 ARlCbDB SupplbrDB MatWtalDB
SalssDB ProdDB Prod08
(4 (b)
Figure 5: Access control trusted (a) to federation DBAs
and (b) to local DBAs
Alternative
1. The federation DBA composes com-
plete LOB schemata into a single schema
GZobalDB.
Based
on this global schema, he derives two subschemata by ex-
tension and filtering,
PersonDB
including customers and
suppliers, and
ConstructionDB
with articles and materials
(see Figure 5.a).
In this approach, component DBAs do not make any
restriction to the data they export to the federation. Thus,
full access control is trusted to the federated DBA, he is
responsible to combine the appropriate classes into sub-
schemata of the federation and to make available to the
distinct users.
Alternative 2.
Each component DBA creates on his
LOB site customized subschemata, already splitting the
local objectbase into information about persons and con-
struction. To the federation DBA of the
PersonDB
and
of the
ConstructionDB,
which may be different, only those
subschemata are made accessible, they finally need. So,
one will compose
CustomerDB
with
SupplierDB
and the
other
ArticleDB
with
MateriaIDB
(see Figure 5.b).
In this approach, component DBAs have control on
their local data and provide access individually. Federation
DBAs may even not know what is the full contents in the
LOBS.
6 RELATED WORK
Recently, there has been an increasing number of proposals
on how to support views in object-oriented systems. Our
approach is fundamentally different in that we make ex-
clusive use of query language expressions (object algebra)
to define views. In contrast e.g., 02 111 and ORION [5] in-
troduce special purpose view definition features, FUGUE
[7] use type hierarchies for information hiding, and POST-
GRES [19] uses the rule system for view simulation.
Moreover, most of them do not consider positioning
view classes in type and class hierarchies. One exception is
a view definition methodology of [ll], where one basic step
is integration of virtual classes into one consistent global
schema. [5] presents a related solution by introducing a
new “view derivation hierarchy” that is orthogonal to the
type and class hierarchies.
Closure was recognized important for schema correct-
ness in [12, 111. The latter presents an algorithm mak-
ing any schema closed by transitively including all range
classes. As we discussed in Subsection 3.2, this approach
is not satisfactory since it brings
in
properties of objects
through the back door, that we intentionally wanted to
filter out.
The approach of database integration by finding cor-
responding properties and proxy objects was also investi-
gated in [15,6]. They introduced for each kind of semantic
relationship between objects a
new
special type of gener-
alization class. In contrast, our solution makes exclusive
use of an algebraic object
view
mechanism, using the pos-
sibility of the
extend
operator to establish links between
LOBS.
The power of views and query languages for access con-
trol was discussed very early for relational systems [18].
[lo] realized that for databases including richer object-
oriented and semantic concepts, an advanced model for
authorization is needed. However, they do not investi-
gate the enhanced possibilities of an object-oriented alge-
bra (encapsulation, type-specific methods) for authoriza-
tion purposes.
7 CONCLUSION
The contribution of this
paper
is three basic schema trans-
formation processors for federated objectbases: schema ez-
dension to add views that are computed by an algebraic
query language;
filtering
to build a closed subschema, and
composition
to put schemata side-by-side.
FOBS are supposed to follow Sheth/Larson’s reference
architecture with five schema levels. The three processors
are said to be complete in the sense, that every transition
between these schema levels can be attained by applying
a combination of them as follows:
External Level
t extension &filter
Federated Level
t composition & extension
Export Level
t extension &filter
Component Level
Nevertheless, the processors do not require fixed levels,
but support incremental evolution from given LOBS to
CUS-
tomized user-oriented FOBS. In fact, one may also see this
as a bottom-up development and design methodology for
FOBS
45
Integration of objectbases was introduced as schema
composition followed by schema extension. This approach
defuses the problem of huge federated schemata, because
there is no need to define such a global view, but instead
only those parts are to be combined that are really needed.
It pays also attention to the fact that LOBS are populated
before they come together in a federation.
Access control and authorization in FOBS was shown
how to be managed by schema extension together with
schema filtering. It was discussed, that access control can
be permitted or denied either locally on LOB level, or glob-
ally on FOB level.
At the beginning, we mentioned that we are restricted
to FOBS with homogeneous data models. Future work
will consider a fourth processor: schema mapping. This
processors is needed to map LOB schemata of different
models/languages into a common data model. First re-
sults are already available from the FEMUS project 121,
where COCOON objectbases and algebra expressions were
mapped to an extended entity-relationship model with an
ER calculus.
References
PI
PI
[31
II
151
PI
171
PI
S. Abiteboul and A. Bonner. Objects and views. In
Proc. ACM SIGMOD,
Denver, Colorado, June 1991.
M. Andersson, Y. DuPont, S. Spaccapietra,
K. YQtongnon, M. Tresch, and H. Ye. The FEMUS
experience in building a federated multilingual data-
base. In Proc.
3st Int’l RIDE-IMS Workshop,
Vienna,
Austria, April 1993.
C. Batini, M. Lenzerini, and S.B. Navathe. A compar-
ative analysis of methodologies for database schema
integration.
ACM Computing Surveys,
18(4), Decem-
ber 1986.
C. Beeri. Formal models for object-oriented data-
bases. In Proc.
1st Int’l Conf. DOOD,
Kyoto, Japan,
December 1989.
E. Bertino. A view mechanism for object-oriented
databases. In
Proc. 3rd Int’l Conf
on
EDBT’92,
Vi-
enna, Austria, March 1992.
J. Geller, Y. Perl, and E.J. Neuhold, Structural
schema integration in heterogeneous multi-database
systems using the dual model. In
Proc.
1st Int ‘I RIDE-
IMS Workshop,
Kyoto, Japan, April 1991.
S. Heiler and S.B. Zdonik. Object views: Extending
the vision. In
Proc. 6th Int ‘1 IEEE Data
Engineering,
Los Angeles, February 1990.
D. K. Hsiao. Federated databases and systems.
VLDB
Journal,
l(l), 1992.
PI
WI
Pll
WI
P31
P41
P51
WI
P71
WI
P91
PO1
W. Kent. The breakdown of the information model
in multi-database systems.
ACM SIGMOD Record,
20(4), December 1991.
F. Rabitti, E. Bertino, W. Kim, and D. Woelk. A
model for authorization for next-generation database
systems.
ACM TODS,
16(l), March 1991.
E.A. Rundensteiner. MultiView: a methodology for
supporting multiple views in object-oriented data-
bases. In
Proc. 18th Int’l Conf. on VLDB,
Vancouver,
Canada, August 1992.
M.H. Scholl, C. Laasch, and M. Tresch. Updatable
views in object-oriented databases. In
Proc. 2nd Int ‘1
Conf.
OR
DOOD,
Munich, Germany, December 1991.
M.H. Scholl and H.-J. Schek. A relational object
model. In Proc.
3rd Int’l Conf. on ICDT,
Paris, 1990.
M.H. Scholl, H.-J. Schek, and M. Tresch.
Object
al-
gebra and views for multi-objectbases. In Proc.
Int’l
Workshop on Distribzlted Object Management,
Ed-
monton, Canada, August 1992.
M. Schrefl.
Object-Oriented Database Integration.
PhD thesis, Technische UniversitZit Wien, Osterreich,
June 1988.
A.P. Sheth and J.A. Larson. Federated database sys-
tems for managing distributed, heterogeneuos, and
autonomous databases.
ACM Computing Surveys,
22(3):183 - 236, September 1990.
S. Spaccapietra, C. Parent, and Y. DuPont. View
integration: A step forward in solving structural con-
flicts.
IEEE Trans. on Knowledge and Data Engineer-
ing,
October 1992.
M. Stonebraker and E. Wong. Access control in rela-
tional databases management systems by query mod-
ification. In Proc.
ACM National Conf.,
1974.
M.R. Stonebraker, A. Jhingran, J. Goh, and
S. Potamianos. On rules, procedures, caching and
views in database systems. In
Proc. ACM SIGMOD ,
Atlantic City, USA, May 1990.
M. Tresch and M.H. Scholl. Mets object management
and its application to database evolution. In Proc.
11th Int’l Conf. Entity-Relationship Approach,
Karl-
sruhe, Germany, October 1992.
46
