A Glimpse at SETS Automated Reification
[ Back to SETS ]

SETS can be shown to supersede the standard relational database calculus. As a matter of fact, it has been taught to Minho's undergrads, for several years now, as a ``do it by calculation'' alternative to conventional database design.

This alternative is illustrated below by ``animating'' a small subset of SETS which leads naturally to 3NF data models. This animation is carried out in the CAMILA rapid-prototyping environment. The laws included in this prototype are numbered according to the lecture notes (Postscript) of a crash course on SETS technology (UNU/IIST, May 97) which the reader may want to have a look at for many details missing here.

The source code of this naive SETS animator (setsan.cam) can be obtained from J.N. Oliveira. Readers interested in a fully general SETS animator implemented on top of genetic algorithm based term-rewriting should get in touch with F.L. Neves.

A SETS refinement target: the relational database model

A SETS-specification data model is said to be compliant with the relational database model if it is a finitary product of expressions of the following kind:

• relations -- (A1*...*An)-set where every Ai is regarded as an ``atomic type'' in the target relational environment;
• mappings -- (A1*...*An)->(B1*...*Bm) where every Ai and Bj is regarded as an ``atomic type'' in the target relational environment.

Moreover,

• several laws of SETS play an important rôle in data model reification, enabling the ``decomposition'' of complex/nested mappings or sequences into tuples of simpler mappings;
• since finite mappings are easily refined into binary relations, this SETS fragment is useful in refining elaborate, finite-mapping/sequence based data models into relational database schemata.
• It has been proved elsewhere (see [Ro93] in the SETS main page) that 3NF is guaranteed by mere application of such laws, among others.

An example: the PPD ``toy'' production database

Consider the following SETS data model for a ``toy factory'' production database:

• this factory builds equipments (E) whose production involves individual components (C) obtained from a second source;
• each individual component has a cost:

        C->$

• components participate, in fixed quantities, in the production of equipments (e.g. PC board ref. X has n integrated circuits of ref. Y), and equipments may contain, in fixed quantities, other equipments as sub-blocks (e.g. personal computer ref. Z has m PC boards of ref. X):

        (E->(C+E)->|N)

  (Nat stands for the set of natural numbers);
• (sub)equipments are stocked along with components in order to be readily available for production:

        (C+E)->|N

The overall formal model is

      ppd=((C+E)->|N)*(C->$)*(E->(C+E)->|N)

so that a production tree exists for each equipment which may involve individual components and/or other production sub-trees.

Automatic calculation of a relational implementation of PPD

We start by loading our CAMILA prototype of a susbset of SETS:

[jno@camila-mobile]$ camila setsan.cam

UM-XMETOO version 1.10.DLL.COMM.USERTYPE (aap/pem/cjr/jj  97/02/26 )
/home/jno/.metoorc")
setsan.cam
?-

First, we check for the laws which have been included in the prototype:

?- laws();
( 96) -- A*1 == A
(101) -- A*(B+C) == (A*B)+(A*C)
(110) -- A->B == (B+1)^A
(124) -- (A+B)->C <= (A->C)*(B->C)
(128) -- A->B->C <= (A->1)*(B->C)
(129) -- A->D*(B->C) <= (A->D)*((A*B)->C)
(130) -- A->B+C <= (A->B)*(A->C)
(134) -- A-seq <= |N->A

Now load the ppd SETS expression:

?- ld(ppd);
x=(((C+E)->|N)*(C->$))*(E->(C+E)->|N)

We just have to apply the ``step-by-step'' method step, which will re-write this expression while telling us which laws have been applied at each step:

?- step();
Law (124)
Law ( 96)
x=(((C->|N)*(E->|N))*(C->$))*(E->1*((C+E)->|N))
 
?- step();
Law (129)
x=(((C->|N)*(E->|N))*(C->$))*((E->1)*((E*(C+E))->|N))
 
?- step();
Law (101)
x=(((C->|N)*(E->|N))*(C->$))*((E->1)*(((E*C)+(E*E))->|N))
 
?- step();
Law (124)
x=(((C->|N)*(E->|N))*(C->$))*((E->1)*(((E*C)->|N)*((E*E)->|N)))

We stop here because the resulting SETS expression already specifies a 3NF relational data-model - we have obtained 6 tables as a relational implementation of ppd:

Comp	Qty
...	...

component stock-level table

C->|N

Equip	Qty
...	...

equipment stock-level table

E->|N

Comp	Cost
...	...

component cost table

C->$

Equip

...

table storing equipments with no production tree yet

E->1

Equip	Comp	Qty
...	...	...

equipment-into-component decomposition table

(E*C)->|N

Equip	Equip	Qty
...	...	...

equipment-into-(sub)equipment decomposition table

(E*E)->|N

NB:

• Attribute idenitifiers such as Equip, Qty etc. have been chosen freely.
• Abstract invariant calculation was deliberately left out, see e.g. the UNU/IIST SETS course for details.