Re: Expressions versus the value they represent

On Apr 13, 10:38 pm, Keith H Duggar <dug..._at_alum.mit.edu> wrote:
> On Apr 13, 3:42 am, David BL <davi..._at_iinet.net.au> wrote:

> > Consider a FOL term (call it T) that under interpretation represents a
> > particular relation of type DirectedGraph. Let GRAPH be a function
> > symbol of arity 1. Under interpretation let GRAPH(T) denote the graph
> > represented by T. This unary function isn't 1-1 and nicely handles
> > the "override" of equality. Indeed GRAPH represents none other than
> > the canonical projection map of the equivalence classes according to
> > graph isomorphism.
>
> > It would seem that the equivalent in the D&D RM would be to introduce
> > a type named GRAPH and its selector function is the canonical
> > projection map described above.
>
> Or to define an ISOMORPHIC function and use that in WHERE (or
> the equivalent) clauses, or to let GRAPH(T) denote simply the
> canonical projection as a DirectedGraph (no need for another
> type), or ...
>
> For example, if you want a "join" where isomorphism is used as
> "equality" rather than simple relational equality it seems any
> of these (and please forgive whatever pseudo SQL appears below):
>
> SELECT *
> FROM GroupA, GroupB
> WHERE ISOMORPHIC(GroupA.DAG, GroupB.DAG)
>
> SELECT *
> FROM GroupA, GroupB
> WHERE GRAPH(GroupA.DAG) == GRAPH(GroupB.DAG)
>
> ...
>
> So what precisely is the problem you perceive with the current
> state of affairs? What can we not currently express/define?

I would say that limiting ourselves to applications where recursive data types aren't required, there is nothing wrong in the current state of affairs assuming adequate use of D&D types are used. Having a rich set of types (and hence selector functions) is analogous to a rich set of function symbols for FOL terms, for which the interpretation of the encoding of a value is in a certain sense explicit for all to see.

However I think some people believe that a more constrained application of the RM promoting TVAs, RVAs and simple built-in types is all that's needed. Then there are those who dislike TVAs and RVAs but rather than use rich data types instead compensate with the introduction of abstract identifiers. I want to counter both of these view points.

I'm not keen on the use of ISOMORPHIC in the where clause because it seems that queries have to be written very carefully to account for the "hidden" semantics. I say they are hidden in the sense that they aren't explicit in the schema expressed in some DDL. It seems a dangerous road to go down. i.e. the schema is implicitly using relations to encode values that are not relations. Of course one could perhaps say that a directed graph IS a relation, but really I think it is dangerous to confuse an equivalence class with its members (at least within a schema).

E.g. I would consider it unsatisfactory to use pairs of integers (numerator and denominator) to directly encode rational numbers (i.e. without an explicit function symbol (or type selector function) to express the intended interpretation). I could imagine by analogy, WHERE clauses all over the place that test whether (numerator,denominator) pairs are equivalent. That's inconvenient, makes errors more likely, and exposes "implementation" details (e.g. numerator is not unique if the encoding isn't canonical).

For complex types it will expose "private" abstract identifiers in a "containing context". That defeats a very desirable characteristic of applications of the RM - that a tuple in a relation can be interpreted as an *independently* verifiable proposition by a domain expert (i.e. independent of all other tuples across all relations). Abstract identifiers that are accessible to a "containing context" defeat that.

As another example, I would like to use an explicit function symbol CIRCUIT to express the intended interpretation of some encoding of an abstract electronic circuit value composed of some arrangement of resistors, capacitors, inductors etc. This is particularly true if I want to express propositions about electronic circuit values in some "containing context". This latter example brings me to an idea that I've had for some time - that it's useful to utilise the full power of the RM on an entire "database value" which is actually just a tuple of named relations to "implement" the most complex data types. i.e. so on the "inside" of this "database value" we have a private context for introducing and using abstract identifiers and named relations, but on the "outside" the thing is treated as a selector function parameterised by those named relations. This is selecting a value which represents some well defined equivalence class over its parameterisation or "implementation".

I think it is well worth paying considerable attention to this little gem that appears in http://en.wikipedia.org/wiki/Equivalence_class:

<quote>
The notion of equivalence classes is useful for constructing sets out of already constructed ones.
</quote>

This provides a valuable tool to help define types in a DDL. i.e. any equivalence relation can give rise to a new and distinct type with a selector function which is the canonical projection. Received on Wed Apr 14 2010 - 11:07:26 CEST