Objects And Binary Relations
Andrew Girow
ABSTRACT
Some aspects and issues of integration of the Binary Relations Model and
object-oriented approach are explained. We start with the simple Binary
Relations Model and add abstraction mechanisms by building orthogonal IS-A
and IS-PART hierarchies. This Binary Relations Model can play two roles. As
a metamodel, it describes object-oriented concepts and can be used as a
metabase for object-oriented design (OOD). As a datamodel, it allows you to
link object applications to a binary database. A C++ library, BRL, based on
binary relations, is then described in the last part.
INTRODUCTION
Objects are becoming the leading software development approach. Capturing
information into an object system has to work according to the basic model,
i.e., its structure of information grouped into objects, its object types
defined as classes, etc. In this text we will, therefore, adapt a more
fundamental view of modelling, inspired by the Binary Relations Model (BRM)
as described in several places in the literature [1], [2], [3].
This does not in any way limit the use of an object-oriented approach since
one can construct algorithms that build the OOP project from the binary
model afterwards. This is, in fact, one of the principal functions of the
BRM that we will briefly describe in the sequel. This structure has many
advantages: conceptual clarity, a higher level of abstraction, different
abstraction mechanisms, closeness to natural language and reasoning
together with formal specifications. Principally, this approach allows use
of a great deal more semantics than a "classical" object modelling
exercise, without sacrificing the foundation of the object model.
ABSTRACTION MECHANISMS IN BINARY RELATIONS
Abstractions are widely used in computer science to help in understanding
complex systems and for data structuring. In data modelling three types of
abstractions are used: generalization, aggregation, and association.
Generalization allows association with a set of symbols or types with one
generalized type. The generalization "symbol-type" is named by
classification, and the generalization "type-type" is a pure
generalization. The generalized type has properties, general for base
types. In other words, properties of the generalized type are inherited by
base types.
Aggregation is an abstraction, by means of which an object can be
constructed from other, base objects. Thus, if a type is a generalized and
aggregate type at the same time, its subtype-objects inherit
property-objects and consequently the properties of these objects.
Association is an abstraction, by means of which associations between types
are established.
Aggregation and generalization can be used together to express structural
and classification aspects of the typing process. The structure of a type
can be presented as an aggregate of base types, and the aggregate can be
generalized. The type classification can be expressed by the generalization
hierarchy, the type structure by the aggregation hierarchy. We can consider
these hierarchies as orthogonal.
Applying the approach "from bottom to top," the abstraction can be
presented as a synthesis of complex objects from the simple ones. At the
beginning, the classification of the symbols allows you to generate types.
The types are connected by the associations, and then by using
generalization and aggregation, new generalized and aggregated types
are constructed.
Binary Relations Model
BRM is a graphical model. Vertexes V of the graph G(V,E) correspond to the
classification "symbol-type", and edges E to the associations of types. The
graph G, that responding to these structural representations and describing
the intention of a binary database has the name of the type graph.
For example, the type graph G presents connections of types
EMP-NO, NAME , TITLE and SALARY (see Fig. 1)
To define a binary relation it is necessary to specify the name of the
relation, a key type, a value type, and a cardinal number:
rel ( keytype, valuetype, relation, cardinal ).
The cardinal number 1 defines the functional relation, N
defines the multiple-valued relation.
For the graph G (see Fig. 1), we have:
rel(EMP-NO, NAME, NAM-OF-EMP, 1)
rel(EMP-NO, SALARY, SAL-OF-EMP, 1)
rel(EMP-NO, TITLE, TIT-OF-MGR, 1)
rel(EMP-NO, EMP-NO, MGR-OF-EMP, N)
rel(EMP-NO, EMP-NO, EMP-OF-MGR, N)
Figure 1. The type graph G.
BRM allows a number of "constraints." For instance, an employee can have
only one name. This constraint has to be included in the NAM-OF-EMP
relation definition. Constraints can be a part of the type operations
specifications. They define constraints, which should be supervised and
supported in the fulfilment of the type operations. Programs in BRM are
objects of the type PROGRAM.
On the level of elements BRM provides the following main
operations:
generator creates an object of a given type;
killer deletes an object;
recognizer returns an object type;
accessor retrieves value object using a given key object;
tester checks up the connection between objects;
updater connects objects;
eraser disconnects objects;
key returns a key object;
value returns a value object.
Figure 2. The BRM structural graph.
As a metamodel, BRM can describe itself. The structural graph
G connecting the main concepts of the BRM is shown in Figure 2. For the BRM
structural graph G (see Fig. 2), we have:
rel(TYPE, PROGRAM, generator, N)
rel(TYPE, PROGRAM, killer, N)
rel(TYPE, PROGRAM, recognizer, 1)
rel(RELATION, TYPE, key, 1)
rel(RELATION, TYPE, value, 1)
rel(RELATION, NUMBER, cardinal, 1)
rel(RELATION, PROGRAM, accessor, 1)
rel(RELATION, PROGRAM, tester, 1)
rel(RELATION, PROGRAM, updater, 1)
rel(RELATION, PROGRAM, eraser, 1)
Abstraction mechanisms
Applying the approach "from bottom to top" we will add
abstraction mechanisms to the BRM.
[ ... skipped... ]
For our example in Figure 1 we have the following induced hierarchies shown
in Figure 3.
Figure 3. Hierarchies induced by G: (a) IS-A hierarchy; (b) Association
hierarchy; and (c) IS-PART hierarchy.
INTEGRATION OF OBJECTS WITH BINARY RELATIONS
The BRM can play two roles in this integration. As a metamodel, it
describes object-oriented concepts and can be used as a metabase for OOD.
As a datamodel, it allows us to link object applications to a binary
database.
We refer to the "classic" Booch's methodology [4].
A class is a set of objects with common structure and behavior. There are
three types of relations between classes: generalization (IS-A hierarchy),
aggregation (IS-PART hierarchy), and association.
Booch's OOD model at the level of logical design has two main parts: a
CLASS STRUCTURE that corresponds IS-A hierarchy and an OBJECT STRUCTURE
that corresponds IS-PART hierarchy. Other relations the OOD model presents
in an OBJECT DIAGRAM.
In terms of BRM, a graph G that responds to these OOD structural concepts
describes the intention of a binary metabase for OOD projects (see Fig. 4).
Figure 4. The G graph describes connections between basic OOP concepts
where (a) corresponds to the OBJECT DIAGRAM (b) corresponds to CLASS
STRUCTURE (c) corresponds to OBJECT STRUCTURE.
A binary metabase for OOD projects (see Fig. 4) can be described by the following relations:
rel(OBJECT, OBJECT, association, N)
rel(CLASS, CLASS, derived-from, N)
rel(CLASS, PROGRAM, constructor, N)
rel(CLASS, PROGRAM, destructor, 1)
rel(CLASS, PROGRAM, funcmember, N)
rel(PROGRAM, CLASS, classutility, N)
rel(CLASS, CLASS, datamember, N)
For example, for the C++ library BRL that implements the BRM we can have
the following fragment of the binary metabase.
derived-from:
(BDB, BOBJECT)
(BLOT, BOBJECT)
(BREL, BOBJECT)
(BRO, BOBJECT)
constructor:
(BREL,BREL)
destructor:
(BREL,~BREL)
funcmember:
(BREL,access)
(BREL,cardinal)
(BREL,erase)
(BREL,iterator)
(BREL,key)
(BREL,test)
(BREL,update)
(BREL,value)
datamember:
(BREL,keyobj)
(BREL,valueobj)
(BREL,crd)
Above we used BRL classes:
BOBJECT
BOBJECT is an abstract class poviding the base for the whole
BOBJECT- based hierarchy. The member functions provide the basic
essentials for all derived classes and the objects they contain.
BDB
A database is a special collection of BREL type objects. The instance class
BDB is derived from BOBJECT, and provides basic functions for storing and
retrieving a collection of binary relations.
BLOT
BLOT is an abstract class derived from BOBJECT. You can use BLOT to
build lexical object classes. Objects are said to be lexical when they
are atomic objects and can be placed in a lexical order.
BREL
The instance class BREL is derived from BOBJECT, and implements an atomic
link between pairs of objects ( binary facts ) belonging to certain object
types. No duplicate fact objects are allowed in a relation. The BREL
recognizes some important constraints that are essential for a correct
database design: If the cardinal of a relation is ONE it defines the
functional link. Each key in a relation is unique. Only one value can be
associated with each key in a relation. If the cardinal of a relation is
MANY it defines a multiple-valued link. With each key in a relation, one or
many values can be associated. Member functions allow you to retrieve the
value object of a fact stored in the relation if you supply the key.
BRO
BRO is an abstract class derived from BOBJECT. You can use
BRO to build complex object classes using binary relations as
bricks.
As we said above, BRM allows us to link object applications to a binary
database. below is simplified C++ code for the BRL to our example.
// EXAMPLE.H It is a very simple example of a database
// definition.
//
#include
// ------------------------------------------------------------
//
// CONCEPTUAL SCHEMA: Non- redundant binary relations
//
// ------------------------------------------------------------
// Objects
CHAROBJ(EMP_NO,6)
CHAROBJ(NAME,40)
LONGOBJ(SALARY,6)
CHAROBJ(TITLE,40)
// Relations
RELATION(EMP_NO,NAME,NAM_OF_EMP,ONE)
RELATION(EMP_NO,SALARY,SAL_OF_EMP,ONE)
RELATION(EMP_NO,TITLE,TIT_OF_MGR,ONE)
RELATION(EMP_NO,EMP_NO,MGR_OF_EMP,MANY)
RELATION(EMP_NO,EMP_NO,EMP_OF_MGR,MANY)
// EXAMPLE.OO It is a very simple example of a database
// definition.
//
// ------------------------------------------------------------
//
// EXTERNAL SCHEMA: Classes and Objects
//
// ------------------------------------------------------------
class EMPLOYEE: public BRO
{
public:
NAM_OF_EMP nameOfEmp;
SAL_OF_EMP salaryOfEmp;
EMPLOYEE() { addGen(&nameOfEmp); addProp(&salaryOfEmp); }
~EMPLOYEE(){}
EMP_NO *empNo() { return (EMP_NO *)object(); }
};
class MANAGER: public EMPLOYEE
{
public:
TIT_OF_MGR titleOfMgr;
MANAGER()
{
addGen(&titleOfMgr);
}
~MANAGER(){}
};
// LOOKUP2.CPP Looks up a manager with the EMP_NO and
// retrieves his subordinates
//
#include "BRL.h"
#include "example.h"
#include "example.oo"
int main( int argc, char *argv[] )
{
if( argc != 2 )
{
cerr << "Usage: lookup2 EMP_NO\n";
return 1;
}
bmachine->start(); // Start up
bdatabase->open("EXAMPLE"); // Opens the database
EMPLOYEE *employee = new EMPLOYEE;
MANAGER *manager = new MANAGER;
EMP_OF_MGR *empOfMgr = new EMP_OF_MGR;
EMP_NO *mgrToLook = new EMP_NO;
employee->open();
manager->open(); // associations
bdatabase->openRel(empOfMgr);
mgrToLook->import(argv[1]);
if( manager->access(mgrToLook) == NULL )
{
cout << "\nNot found\n";
}
else
{
cout << manager->empNo() << ": ";
cout << manager->titleOfMgr() << "\n";
cout << manager->nameOfEmp() ;
cout << manager->salaryOfEmp() << "\n";
cout << "\nSUBORDINATES: \n";
BRI &emplist = empOfMgr->iterator();
emplist.firstThat(manager->empNo());
while(emplist && empOfMgr->key()->isEqual(*manager->empNo() ) )
{
employee->access(empOfMgr->value());
cout << " " << employee->empNo() << ": ";
cout << employee->nameOfEmp() ;
cout << employee->salaryOfEmp() << "\n";
++emplist;
}
delete &emplist;
}
delete &manager;
delete &employee;
delete &empOfMgr;
delete &mgrToLook;
bdatabase->close();
bmachine->stop();
return(0);
}
CONCLUSIONS
In this article, the integration of the Binary Relations Model and the
object-oriented approach were introduced. We started with the simple
Binary Relations Model and added abstraction mechanisms. Two roles
(metamodel and datamodel) of the Binary Relations Model in this integration
were described. The C++ library BRL, based on
binary relations, were then described.
References
[1] J. R. Abrial. Data semantics, in
Database Management Systems, J.W. Klimbie and K. L. Koffeman,
eds., North Holland, New York, 1974.
[2] G. Bracchi, P. Paolini, and G.
Pelagatti. Binary logical associations in data modelling, in
Modelling in Data Base Management Systems, G.M. Nijssen, ed.,
North-Holland Publishing, Amsterdam, 1976.
[3] M. E. Senko. DIAM as a detailed
example of the ANSI SPARC architecture, in Modelling in Data Base
Management Systems, G.M. Nijssen, ed., North-Holland Publishing,
Amsterdam,1976.
[4] G. Booch. Object-Oriented Design
with Applications, Benjamin/Cummings, Menlo Park, CA, 1991.
©1996 SIGS Publications, Inc., New York, NY, USA. All
Rights Reserved.
