[Skip Navigation] [CSUSB] / [CNS] / [CSE] / [R J Botting] / [ MATHS ] / logic_44_n-aryrelations
[Contents] [Source Text] || [Notation] || [Copyright] || [Contact] [Search ]
Fri Feb 1 14:23:51 PST 2013

Contents


    N-ary Relations and n-tples.

      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,
      Table
      RealRealReal
      xysqrt(x^2+y2)

      (Close Table)

      [ notn_9_Tables.html ]

      Relational Operators

      Given a collection of sets of tuples, Codd's Relational operations are already define in MATHS:
      Table
      RelationalMATHS
      Projection Relation.(Names_of_components)
      Selection Relation and Condition
      Product variables(Relation1) and variables(Relation2)
      Join Relation1 and Relation2 and Net{Connection }
      Union Relation1 | Relation2
      Intersection Relation1 & Relation2
      Difference Relation1 ~ Relation2

      (Close Table)

      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://cse.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).

      Dynamics for data bases and data structures

      1. database::= See 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
      2. S'=S|A
      3. or
      4. S:|A
      5. 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

      6. { s:S || s.p not in D }
      7. or
      8. S ~ /p(D)
      9. 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><T) The operation is to first delete items and then add the changed ones, or

      10. S' = { t:T || for some s:S ( (s,t) in U ) },
      11. S' = S.U,
      12. or
      13. S :.U.

        Finally there are often preconditions on addition, deletion and update operations.

        Useful operations on data

        So a typical collection of operation might be:
      14. SIMPLE_UPDATE_DELETE_ADD::=SIMPLE_UDA.
      15. SIMPLE_UDA::=
        Net{
        1. S::Finite_set(T).
        2. For A:Finite_set(T), Add(A)::= map[S](no A & S and S:|A).
           		Students.Add({dick,jane}).
           		Students.Add(jo).
          (jo will be coerced to be a set {jo}).

          Note: Creating a new object will be matter of constructing it and then adding it to the right set.

        3. For A, Delete(A)::=map[S](A==>S and S:~A).
           		Student.Delete(jo).
        4. For A, p:T->P, Delete(p,A)::= map[S](A==>p(S) and S:~/p(A)).
        5. Remove all elements of S that fit property p.
           		Student.Delete(sid, "123-45-6789").

        6. For U: @(T,T), Update(U)::=map[S](cor(U)==>S and S :.U).
          		Student.Update(age'=age+1).

        }=::SIMPLE_UDA.

      16. SIMPLE_UPDATE_DELETE_ADD_WITH_KEY::=SIMPLE_UDA_WITH_KEY.
      17. 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 not needed to identify what is being deleted,

        9. 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><value pairs(@(K,V)) into elements that fit in S:

        10. For U:@(K,V), Update_keys(U)::=U in K(any)-(0,1)V and U.1st==>S.k and S'=S ~/k(1st(U)) | U./(k,d).
        11. (unique1)|-/(k,d) in (K><V) --- S.

          For example Update_keys("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:

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

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

    Notes on MATHS Notation

    Special characters are defined in [ intro_characters.html ] that also outlines the syntax of expressions and a document.

    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 might be described by Net{radius:Positive Real, center:Point, area:=π*radius^2, ...}.

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

    Notes on the Underlying Logic of MATHS

    The notation used here is a formal language with syntax and a semantics described using traditional formal logic [ logic_0_Intro.html ] plus sets, functions, relations, and other mathematical extensions.

    For a more rigorous description of the standard notations see

  1. STANDARD::= See http://www.csci.csusb.edu/dick/maths/math_11_STANDARD.html

    Glossary

  2. above::reason="I'm too lazy to work out which of the above statements I need here", often the last 3 or 4 statements. The previous and previous but one statments are shown as (-1) and (-2).
  3. given::reason="I've been told that...", used to describe a problem.
  4. given::variable="I'll be given a value or object like this...", used to describe a problem.
  5. goal::theorem="The result I'm trying to prove right now".
  6. goal::variable="The value or object I'm trying to find or construct".
  7. let::reason="For the sake of argument let...", introduces a temporary hypothesis that survives until the end of the surrounding "Let...Close.Let" block or Case.
  8. hyp::reason="I assumed this in my last Let/Case/Po/...".
  9. QED::conclusion="Quite Easily Done" or "Quod Erat Demonstrandum", indicates that you have proved what you wanted to prove.
  10. QEF::conclusion="Quite Easily Faked", -- indicate that you have proved that the object you constructed fitted the goal you were given.
  11. RAA::conclusion="Reducto Ad Absurdum". This allows you to discard the last assumption (let) that you introduced.

( End of document ) <<Contents | Top