.Open N-ary Relations and n-tples.
. History
Norbert Wiener was the first mathematician to publicly identify n-ary relations with subsets of n-tples:
For Sets X,Y,..., @(X,Y,...) ::= @(X>< ...).
For Sets X,Y,..., variables x,y,..., (rel [x:X,y:Y,...](W(x,y,...))) ::= {n:(X><...)||W(n(1),n(2),...)}.
For Sets X,Y,..., variables x,y,..., (rel [x,y,...](W(x,y,...))):@(X,Y,...) ::= {n:(X><...)||W(n(1),n(2),...)}.
So if R is an n-ary relation connecting n sets X1,X2,...,X[n], then we can model it as a set of simple objects with functions mapping R into X1, X2, ...X[n]:
1st:: R->X1, 2nd::R->X2, 3rd::R->X3, ... i.th::R->X[i], ... n.th::R->X[n].
As examples, consider part of a model of a college where a class has
a subject, units, time, room, etc.:
.Net
1st:: Class -> Subject,
2nd:: Class->Units,
3rd::Class->Time,
4.th::Class->Time,
5.th::Class->Room,
...
.Close.Net
or a formal model of addition where (a,b,c) in Sum iff a+b=c.
.Net
1st:: Sum->Number,
2nd::Sum->Number,
3rd::Sum->Number.
.Close.Net
The mappings can be quantified:
If
1st in R(l1..h1)-(1) X1, 2nd in R(l2..h2)-(1)X2, 3rd in R(l3..h3)-(1)X3, ...
then the Mathematical Pigeonhole Principle tells us that:
(pigeon_hole)|- l1*|X1| <= |R| <= h1*|X1| and l2*|X2| <= |R| <= h2*|X2| and ...
Codd discovered and publicized procedures for constructing a set of simple n-ary relations which can support a set of given data. He also argues that instead of n-tples it is better to use labeled tuples and to talk about tables rather than relations. Finally he constructed an extension of the calculus of Binary Relations which is capable of handling many data retrieval problems.
In MATHS n-tples are generalized to labeled tples and powerful ways of documenting them are available,
.See http://www/dick/maths/math_12_Structure.html
.See http://www/dick/maths/notn_4_Re_Use_.html
.See http://www/dick/maths/notn_15_Naming_Documentn.html
.See http://www/dick/maths/notn_13_Docn_Syntax.html
. Convenient Notations
The ".Table" format is a simple way to encode a relationship:
.As_is .Table X Y Z ...
.As_is .Row x y z ...
.As_is ...
.As_is .Close.Table
When rendered something like this:
Pythagoras::=following,
.Table Real Real Real
.Row x y sqrt(x^2+y2)
.Close.Table
.See http://www/dick/maths/notn_9_Tables.html
. Relational Operators
Given a collection of sets of tuples, Codd's Relational operations are already
define in MATHS:
.Table Relational MATHS
.Row
.Key Projection
.Item Relation.(Names_of_components)
.Row
.Key Selection
.Item Relation and Condition
.Row
.Key Product
.Item variables(Relation1) and variables(Relation2)
.Row
.Key Join
.Item Relation1 and Relation2 and Net{Connection }
.Row
.Key Union
.Item Relation1 | Relation2
.Row
.Key Intersection
.Item Relation1 & Relation2
.Row
.Key Difference
.Item Relation1 ~ Relation2
.Close.Table
.Open Conceptual Models
. Basis
Any `n`-ary relation is expressible as a set of `n` maps from a set of `n`-tpls into the components - this leads to the Mathematical model of `structure` and a way to interpret complex data types as a collection of simple independent abstract models. Typically each data type is a set of `n`-tpls with the projection operators onto the component sets.
These maps connect the sets as arcs in a higraph.
. Entities and Relations
In this model it is not necessary (and it can be a waste of time) to distinguish a priori whether you have an entity or a relation. At the logical or conceptual level they are both sets of more or less complicated sets. Similarly it is wise to avoid early commitment as to any particular technique (relational, object, hierarchic, network). These decisions can be delayed until the problem itself is sorted out.
. Diagram
When there are many disjoint sets and at most one map connects each set to another one set then a list of set names determines a unique operator sets of one set into sets of another set. Such a list is called a navigation path. To help determine valid paths, (where maps fit each other) a digraph can be shown with nodes for the sets and arcs for the maps. Such a digraph is called a conceptual model or Bachman diagram.
. Quantification
An important validation step - and preparation for performance analysis - is to quantify how many of each set of tpls there are. Similarly for each of the maps connecting the sets of tpls, a number (or set of numbers) needs to be documented showing how many elements correspond to a single projected image on each component. The mathematical Pigeon-hole Principle can now be used to check whether the model makes sense:
For x:R -> X, |X|*min{ |A| || for some y, A=y./x} <= |R| |X|*max{ |A| || for some y, A=y./x}
. Access Paths
A shorthand to combine many relations and sets together is essential for
documenting long paths through data bases. For example, given a class
we can find what room it is in, and from there what building and campus:
Class..Room..Building..Campus.
For A:@T1,B:@T2, if one @(A,B) then A..B::= the(R:@(T1>b.
(defs)|- {a};B=a+>b.
(defs)|- /(A..B)=B..A.
So for example: Widgets..Prices;min;Prices..Widgets -- find least cost widgets.
.Close Conceptual Models
.Open Z-like Operators
Much of the elegance and power of Z comes from being able to describe change in a state that is defined in terms of sets and binary relations:
theory_of_relations::=http://www/dick/maths/logic_40_Relations.html.
(theory_of_relations)|- A \dashed_triangle_left R = ~A;R. -- delete pairs with (1st) in A
(theory_of_relations)|- R \dashed_triangle_right B =R;~B.-- delete pairs with (2nd) in B
(theory_of_relations)|- For T1,T2, R, S:@(T1,T2), f \circle_plus g= f~>g. -- replace pairs in f by pairs in g with same (1st).
.Close
.Open Dynamics for data bases and data structures
database::=http://www.csci.csusb.edu/dick/maths/math_13_Data_Bases.html.
. Idea
To specify certain transaction however
it is useful to be able to generalize the above operators on binary relations
above to work on n-ary relations and sets of tpls. Adding new items is easy, suppose we
have a structured type `T` and `S` is a subset of `T` and `A` a subset of
`T` then
S'=S|A
or
S:|A
describes the addition of the elements in A to
S.
Deletion is more complex because it is often described as deleting all
records with a particular property - without giving the values of all
variables. For example a typical command would be to delete the record of
an object with identifier "123-45-678" what ever other values it has.
Suppose we have a structured type `T` and a projection operation `p` into
another type `P` (typically a single attribute/variable, or a list of them)
then if `S` is a subset of `T` and `D` a subset of `P` then we can
describe the removal of all elements in S that project into D as
{ s:S || s.p not in D }
or
S ~ /p(D)
Hence, a specification might indicate that
a system must be able to execute actions that implement or realize `S:~/p(D)`.
An update operation is best specified in terms of S being updated by a set
of changes U where each element in U is a pair (an old item, a new item).
So U:@(T>S and S:~A).
.As_is Student.Delete(jo).
For A, p:T->P, Delete(p,A) ::= map[S](A==>p(S) and S:~/p(A)).
Remove all elements of S that fit property p.
.As_is Student.Delete(sid, "123-45-6789").
For U: @(T,T), Update(U) ::=map[S](cor(U)==>S and S :.U).
.As_is Student.Update(age'=age+1).
}=:: SIMPLE_UDA.
SIMPLE_UPDATE_DELETE_ADD_WITH_KEY::=$SIMPLE_UDA_WITH_KEY.
SIMPLE_UDA_WITH_KEY::=Net{
In a normalized data base or set of classes, each class
(entity type) has a key attribute that uniquely identifies objects in
the class (instance or entities). Suppose that S is such a class:
S::Finite_Sets, relationship./class/entity type
K::Finite_sets, set of key values.
D::Finite_sets, set of data values.
A simple example in the USA is if S is a set of records about people
and the key is their Social Security number.
The objects in set S have an identifier and data parts:
key::S->K.
data::S->V.
k:=key, d:=data, shorthand.
|-(unique1): (k,d) in S --- K >< V.
|-(unique2): k in S (0..1)-(1)K.
Deletion is expressed typically in terms of a set of key values,
because the other data is not needed to identify what is being deleted,
For D:@K, Delete_keys(D) ::= D==>S.k and S' = S ~ /k(D)
For example: Delete_keys({"123-45-6789"}).
Updates do not need to describe the whole item being removed,
just it's key, and so is given a set of key+value pairs, however
we have to be careful to convert the set of key>S.k and S'=S ~/k(1st(U)) | U./(k,d).
(unique1)|- /(k,d) in (K>("Dick Botting", ...) ).
Addition of new items must still provide complete information on both key+data and must not lead to more than one item having the same key value:
For A:@S, Add_keys(A) ::=A.(k,v) in K(0,1)-(1)V and no (A.k & S.k) and S'=S|A.
For example, Add_keys({("123-45-6789", "Dick Botting", ...)}).
It is easy to show that the properties (unique1) and (unique2) above are preserved by these operations.
}=:: SIMPLE_UDA_WITH_KEY.
. Exercise
Repeat the above analysis only replacing sets by (a) bags/multisets, (b) fuzzy sets.
. State Machines
Note that these changes can be derived from a simpler model of how the entities themselves change.
It turns out the finite state machines and grammars are a neat way to analyse
the behavior of objects in a system.
.Close
.Close N-ary Relations and n-tples.