History

Norbert Wiener was the first mathematician to publicly identify n-ary relations with subsets of n-tples:
1. For Sets X,Y,..., @(X,Y,...)::= @(X><Y>< ...).
2. For Sets X,Y,..., variables x,y,..., (rel [x:X,y:Y,...](W(x,y,...))) ::= {n:(X><Y><...)||W(n(1),n(2),...)}.

3. For Sets X,Y,..., variables x,y,..., (rel [x,y,...](W(x,y,...))):@(X,Y,...) ::= {n:(X><Y><...)||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]:

4. 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

   1. 1st::Class -> Subject,
   2. 2nd::Class->Units,
   3. 3rd::Class->Time,
   4. 4.th::Class->Time,
   5. 5.th::Class->Room,
   6. ...

   
   (End of Net)
   
   or a formal model of addition where (a,b,c) in Sum iff a+b=c.
   Net
   1. 1st::Sum->Number,
   2. 2nd::Sum->Number,
   3. 3rd::Sum->Number.

   
   (End of Net)
   
   

   The mappings can be quantified: If

5. 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:
   
6. (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, [ math_12_Structure.html ] [ notn_4_Re_Use_.html ] [ notn_15_Naming_Documentn.html ] [ notn_13_Docn_Syntax.html ]

   Convenient Notations

   The ".Table" format is a simple way to encode a relationship:

    		.Table X	Y	Z	...

    		.Row	x	y	z	...

    		...

    		.Close.Table

   When rendered something like this:
7. Pythagoras::=following,

   	Real	Real	Real
   	x	y	sqrt(x^2+y2)

   [ notn_9_Tables.html ]

   Relational Operators

   Given a collection of sets of tuples, Codd's Relational operations are already define in MATHS:

   Relational	MATHS
   Projection	Relation.(Names_of_components)
   Selection	Relation and Condition
   Product	variables(Relation1) and variables(Relation2)
   Join	Relation1 and Relation2 and Net{Connection }
   Union	Relation1 or Relation2
   Intersection	Relation1 and Relation2
   Difference	Relation1 not Relation2

   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:
   1. 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:
   2. Class..Room..Building..Campus.

   3. For A:@T1,B:@T2, if one @(A, B) then A..B::= the(R:@(T1><T2)||R:@(A,B))

      Using semicolons inside operations is confusing to the eye and other simple parsers.

   4. For A:@T1,B:@T2, C:@T3, A..B..C::= A..B;B..C

      Given a para-regular expression in a context that requires a relation (eg... after a period) with items that are names of sets like A,B and C above then (A B C) means A..B..C and #R means do(R). The other operators are treated literally ( "|" indicates union, "&" intersection. "~" complement,... ). For example (Faculty Section Student) might be a table showing which faculty teach student various sections.

      Also note the following theorems:
      

   5. (defs)|-A;{b}=A+>b.
      
   6. (defs)|-{a};B=a+>b.
      
   7. (defs)|-/(A..B)=B..A.

      So for example: Widgets..Prices;min;Prices..Widgets -- find least cost widgets.

   . . . . . . . . . ( end of section Conceptual Models) <<Contents | End>>

   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:
   1. theory_of_relations::= See http://csci.csusb.edu/dick/maths/logic_40_Relations.html.
      
   2. (theory_of_relations)|-A \dashed_triangle_left R = ~A;R. -- delete pairs with (1st) in A
      
   3. (theory_of_relations)|-R \dashed_triangle_right B =R;~B.-- delete pairs with (2nd) in B
      
   4. (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).

      Formal analysis delays these until a network of cooperating classes of objcts has been developed:

   5. database::= See http://www.csci.csusb.edu/dick/maths/math_13_Data_Bases.html.

      To specify certain transaction however it may be useful to be able to generalize the operators on binary relations above to work on n-ary relations. 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 - but not 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 the following 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><T) The operation is to first delete items and then add the changed ones, or S' = { t:T || for some s:S ( (s,t) in U }, `S' = S.U, or S :.U.

      Finally there are often preconditions on addition, deletion and update operations. So a typical collection of operation might be:

   6. SIMPLE_UDA::=
      Net{

      1. Add(A)::= no A & S and S:|A.
      2. Delete(D)::= D==>p(S) and S:~D.
      3. Update(U)::= cor(U)==>S and S :.U.

      
      }=::SIMPLE_UDA.

   7. 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:
      1. S::Finite_Sets, relationship./class/entity type
      2. K::Finite_sets, set of key values.
      3. 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:

      4. key::S->K.
      5. data::S->V.
      6. k:=key, d:=data, shorthand.
         
      7. |- (unique1): (k,d) in S --- K >< V.
         
      8. |- (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 needed to identify what is being deleted,

      9. For D:@K, Delete(D)::= D==>S.k and S' = S ~ /k(D)

         For example: Delete({"123-45-6789"}).

         Updates no longer need to describe the whole item being removed, and so give a set of key+value pairs:

      10. For U:@(K,V), Update(U)::=U in K(any)-(0,1)V and U.1st==>S.k and S'=S ~/k(1st(U)) | U`.

          For example Update("123-45-6789"+>("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:

      11. For A:@S, Add(A)::=A.(k,v) in K(0,1)-(1)V and no A.k & S.k and S'=S|A.

          For example, Add({("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.

      Note that these changes can be derived from a simpler model of how the entities themselves change.

   . . . . . . . . . ( end of section Z-like Operators) <<Contents | End>>

. . . . . . . . . ( end of section N-ary Relations and n-tples.) <<Contents | End>>

Notes on MATHS Notation

Proofs follow a natural deduction style that start with assumptions ("Let") and continue to a consequence ("Close Let") and then discard the assumptions and deduce a conclusion. Look here [ Block Structure in logic_25_Proofs ] for more on the structure and rules.

The notation also allows you to create a new network of variables and constraints. A "Net" has a number of variables (including none) and a number of properties (including none) that connect variables. You can give them a name and then reuse them. The schema, formal system, or an elementary piece of documentation starts with "Net" and finishes "End of Net". For more, see [ notn_13_Docn_Syntax.html ] for these ways of defining and reusing pieces of logic and algebra in your documents. A quick example: a circle = Net{radius:Positive Real, center:Point}.

For a complete listing of pages in this part of my site by topic see [ home.html ]

Notes on the Underlying Logic of MATHS

For a more rigorous description of the standard notations see