Re: Expressions versus the value they represent

On Apr 13, 3:42 am, David BL <davi..._at_iinet.net.au> wrote:
> On Apr 12, 11:35 pm, Keith H Duggar <dug..._at_alum.mit.edu> wrote:
> > On Apr 12, 7:09 am, David BL <davi..._at_iinet.net.au> wrote:
> > > I think the problem is how to define a formal semantics, such that
> > > under interpretation a relation or tuple is able to encode something
> > > else (e.g. an image, string, triangulated surface etc). More
> > > importantly, how is the equality operator which can be regarded as
> > > predefined on relations and tuples somehow overridden to comply with
> > > the interpretation? Also note that the RM operators are defined in
> > > terms of equality of attribute values. So which version of equality
> > > is used on RVAs?
>
> > > An interpretation on nested terms is very simple and elegant.
> > > Equality can be treated as a predicate symbol. How is an
> > > interpretation defined on nested relations?
>
> > Ok, let me make sure I understand this correctly by making up
> > a concrete example. Suppose for example I have a relation with
> > a DirectedGraph attribute where DirectedGraph is a relation
> > valued attribute with header {NodeA : Node, NodeB : Node} under
> > an interpretation "there is an edge from NodeA to NodeB".
>
> > Now given those choices the question arises how to define
> > "equality" because The RM already defines a strict equality
> > for relations which would/could be applied to these RVAs but
> > under our interpretation we may require that "equality"
> > instead be defined as graph isomorphism.
>
> > So it seems we have a problem of how to "override" the equality
> > operator (say "=") such that it is consistent with our desired
> > semantic interpretation.
>
> > Is this what you mean?
>
> Yes.
>
> 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?

KHD Received on Tue Apr 13 2010 - 16:38:46 CEST