Relations

David to prepare this lecture.
I'm putting down my thoughts in outline form.

This lecture will present the basic definitions for relations and
their properties, give lots of examples and a little theory,  
define operations on relations,
present some of the properties of these operations.

Then start going into special kinds of relations: DAGs, partial orderings,
equivalence relations, graphs, trees.
Give the basic theory for DAGs, pos, and equivalence relations.
(Next lecture will cover graphs and trees.)

A new goal for this lecture is to provide a connection with some later
modeling work done by Daniel Jackson in his research, which is 
starting to be used in 6170.
Daniel has developed a language, Alloy, for talking about binary
relations, and has a toolset for program documentation and validation
that uses Alloy.
Alloy is used for talking about relationships between objects that
arise in programs.
This will require some new course development---working in some
examples suggested by Daniel and the theory they suggest.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

Sample lecture outline follows.
My hand-written notes from Fall98 follow this outline, so you might
find it helpful to look at those.


\section{Relations and their properties}

Define binary relation, ternary, n-ary,...

Properties: reflexive, irreflexive, symmetric, antisymmetric,
transitive, total (any pair related one way or the other)

Give lots of examples.

Ways of representing relations (by defining properties, lists,
adjacency matrices).
Examples.
Also by ``network diagrams'', which are the usual pictorial
representations we use when we talk about ``digraphs''.
I just define ``digraph'' to be the same thing as ``binary relation''.
(Allows self-loops, as Rosen does.)
When we say ``digraph'', we usually have a certain kind of
representation in mind.


\section{Paths in relations}

Define.

Special cases: circuit, cycle, simple path

Examples.

Reachability (of one element from another, in a relation)

(Strong) connectivity

Theorems?
Maybe ``reachable implies reachable in at most n steps'', where n is
number of elements in (finite) relation.

\section{Operations on relations}

Relational operators:
Union, restriction, projection, join,...(I'd look at relational db ops
and the ops used by Daniel, to make sure I'd defined all the
interesting ones).

Relational composition

Transitive closure

Definitions, examples.

Theorems?
Some relational algebra identities?


\section{DAGs}

Define, digraph (binary relation having no cycles (including no
self-loops).

Example: Course prereqs.

Critical path

Theorem about scheduling in number of stages equal to length of
longest path.

Examples: Program digraphs

\section{Posets}

Define.

Theorem: Poset has no cycles of length geq 2.

Representation of finite poset by Haase diagram (leaves out some
edges).

Any poset has a total ordering.
Prove this theorem here?  Maybe return to it later. 

\section{Equivalence relations}

Define

Can get partitions from.

Examples


%%%%%%%%%%

Then for the next lecture, I'd go on, defining graphs as irreflexive
symmetric graphs, and trees as connected graphs, no cycles.
Then do some collection of the basic theorems about each.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

New material:

To focus the new material, I got some examples from Daniel.
Here they are, just as he sent them to me.  

1. railway lines:

basic elements
-- set of stations S
-- each line is a relation L: S -> S

conditions
-- reachability: can get from s1 to s2 if (s2 in s1.*L)
-- symmetry: might require L = ~L
-- connectivity: from any one station, can reach another (all s1, s2: S | s1in s2.*L)

can also model separate lines as different relations L_i
-- specify intersection points
-- routes involving using more than one line (with join and closure)

2. geneaology:

basic elements
-- sets of persons, men, women, etc
-- relations such as parent: Person -> Person and spouse: Person -> Person

conditions
-- biological: nobody is her own ancestor
-- definitional: nobody married to himself
-- social: no bigamy, incest, etc

3. caching memory:

basic elements
-- cache and memory are relations from Addr to Data
-- keep set of Addr to represent dirty entries

conditions
-- express cache coherence
-- describe non-deterministic dropping policy

4. mapping ADT

basic elements
-- mapping is a function from Key to Val

conditions
-- model operations of the datatype as simple formulas
        eg, Lookup (k: Key, v: Val) {result = k.m && m = m'}
-- express algebraic properties: insert followed by lookup, etc


I'll just give some preliminary thoughts about what I think we should
do with these examples, where they fit into the outline above.
My basic idea is to use these examples repeatedly, wherever they
illustrate something we are presenting.
(Not to present the examples as big units themselves.)

I think Daniel is focusing on a particular language for expressing
ideas involving relations.
Our job is to pick apart the math ideas underneath.

1. The case of a single railway line is similar to examples we have
already.
(set of computers, relation R ``connected directly by a wire'')
We could add it to the initial list of examples of relations.
Can use it to illustrate the notions of reachability, symmetry, strong
connectivity when we define them.

The case of multiple railway lines looks like an illustration for
some relational operations (union---is that the same as ``join''?,
transitive closure).
I'm not sure about what Daniel means by ``specify intersection
points''.
We should ask, in case there's something else interesting here we
might define.
It must have something to do with reachability.

2. The genealogy example provides nice illustrations of relations and
their properties.
For relational composition.

I'm not sure what to do with Daniel's ``conditions'' here.
Are these definitions or theorems?
If theorems, then what are the definitions from which they follow?

3. The caching memory example is too sketchy for me to tell what
Daniel means.

I can see some examples of relations here (cache and main mem as
relations between addresses and data).

Actually, they are functions, possibly partial functions.
This suggests we might want to include ``being a function'', or
something like that, in the list of basic properties of relations.
That's nice---we might define two properties:
--(function) each first component has at most one second component
and
--(partial function) each first component has exactly one...

Beyond this, I'm not sure what to do with the dirty entries, cache
coherence, and nondeterministic dropping policy ideas.
Those seem to me to fit in better when we talk about algorithms and
state machines.
They seem to be referring to dynamic behavior of a system, unlike the
railway lines and genealogy examples, which just refer to static
relationships among data elements.
???
Needs work.

4. The mapping ADT is a kind of object, whose state is a simple
(partial functional) relation. 
When Daniel talks about the operations and their algebraic properties,
he is talking about the behavior of such a state machine.
Let's use this one when we do state machines.