Expressions versus the value they represent

#11

On Apr 12, 10:57 pm, Bob Badour <bbad... (AT) pei (DOT) sympatico.ca> wrote:

Quote:

David BL wrote:
On Apr 12, 2:37 pm, Keith H Duggar <dug... (AT) alum (DOT) mit.edu> wrote:

On Apr 12, 1:13 am, David BL <davi... (AT) iinet (DOT) net.au> wrote:

snip

The term ellipse(point(0,0),1,1) is distinct from circle(point(0,0),1)
even though we may regard them as both encoding a unit circle.

What is the point here? If we are talking about a multi-sorted FOL
then those two terms have distinct types. If either is equal to some
other expression say "UnitCircle()" or whatever, then that must be
derivable from the stated axioms and type definitions.

Actually I was considering single sorted FOL with equality. Sorry for
not being clear.

My point was that under interpretation, distinct terms can represent
the same value. This leads to an equivalence relation on terms. I was
actually thinking about an analogy to the D&D type system (where
circle is a subtype of ellipse).

The type system in question is a conditional. It is predicated on
someone wanting something like inheritance in their type system. If you
want something like that, then D&D show how to do it with some consistency.

If you don't want a type system with something like inheritance, don't
do that.

Agreed. In any case I think the D&D approach translates nicely into
definitions of equivalence of FOL terms, so it should work very well
in practise. Also I think it's wrong to expect terms to be unique in
general. E.g. 3 = 1+2 = 1+1+1 = 6/2 = ....

Even so, canonical representations of values appears very useful (both
at an abstract level where it can allow equality to be defined
implicitly) and at the physical implementation level (where testing
for equivalence can otherwise be computationally expensive). The idea
of a Most Specific Type of a value has utility for canonical
representations of values.

BTW the possrep idea is related to this discussion. E.g.
polar(1,pi) = cartesian(-1,0) is an example of equivalence of two FOL
terms under interpretation.

#12

On Apr 13, 1:51 am, Bob Badour <bbad... (AT) pei (DOT) sympatico.ca> wrote:

Quote:

Anyhow, interpretation is
orthogonal and therefore irrelevant to both FOL and RM.

I agree. However I consider the topic of my post to concern the
problem of how to encode values on a computer, in which case a formal
semantics is required.

Got it.

Perhaps it would be worth discussing whether that is a fundamental
requirement in database theory? I consider "data" to mean "encoded
value".

Data means information represented suitably for mechanical processing.
The information might be a value or might be something else.

I'm having trouble imagining what information could be if it's not a
value. It appears sufficient to me. For example, if information is
sent between two parties, isn't it sufficient to assume that a value
has been sent? Is the word "information" meant to be informal, as
for example when someone receives information through their senses
(e.g. smelling their socks), but we cannot hope to formalise the
information using a value? Even so, wouldn't information suitable
for machine processing necessarily be a value?

#13

On Apr 12, 11:35 pm, Keith H Duggar <dug... (AT) alum (DOT) mit.edu> wrote:

Quote:

On Apr 12, 7:09 am, David BL <davi... (AT) iinet (DOT) net.au> wrote:

On Apr 12, 2:37 pm, Keith H Duggar <dug... (AT) alum (DOT) mit.edu> wrote:
Hopefully we can agree that since there is no interpretation defined
in the RM nor FOL that there are not "multiple phases" nor "playing
around" nor any other of the problems above.

Yes I agree with that, but I actually want to consider the problems
that arise under interpretations.

Ok, cool. Thanks for this and the other clarifications. Now I'm
a bit clearer on understanding what you are exploring. However,
are we agreed that in the context of RM this is what we would
call the "physical" layer?

I don't know if I fully appreciate what the "physical layer" means.
I thought it had to do with database implementation details, such as
memory and disk layout, hashing, B+Trees etc.

Quote:

For example, suppose that we define a particular interpretation
that maps the ellipse and circle terms to particular structures
say sets over which we define various other axioms (perhaps even
including axioms referring to natural (as in physical world)
observations.

I'm treating an interpretation (on a FOL) as a very formal concept. A
set must be given over which quantification takes place, each function
symbol must be associated with a particular function and each
predicate symbol with a particular relation. An interpretation is
parameterised by particular functions and relations that are pure
mathematical abstractions that cannot be defined in terms of informal
objects that exist in time and space.

Quote:

Then I would argue that even though these sets
are not bits and bytes they are, none-the-less, "physical" in
so far as the RM is concerned. Would you agree?

I would tend to say no although I'm not entirely sure what you mean.
I would say all pure mathematical formalisms like the RM, FOL or a
formal semantics over a FOL give us physical independence because they
are mathematical formalisms divorced from the physical.

Quote:

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.

#14

On Apr 12, 10:35 pm, paul c <toledobythe... (AT) oohay (DOT) ac> wrote:

Quote:

David BL wrote:

...

One of my main motivations here is to question the whole premise
behind RVAs, which I have assumed are used to /encode/ attribute
values within parent relations. I don't believe the RM should be
allowed to play around with interpretation after the fact. Having
multiple phases of interpretation seems extravagant, unnecessary and
ill defined to me. I think FOL can encode all imaginable data types
effectively using nothing more than nested terms with a single
interpretation step.
...

Within D&D's approach I don't think RVA's are at all 'ill defined'.

I agree. I think D&D would say a relation always represents itself.
That avoids problems but restricts their utility.

#15

On Apr 13, 3:42 am, David BL <davi... (AT) iinet (DOT) net.au> wrote:

Quote:

On Apr 12, 11:35 pm, Keith H Duggar <dug... (AT) alum (DOT) mit.edu> wrote:
On Apr 12, 7:09 am, David BL <davi... (AT) iinet (DOT) 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

#16

On Apr 13, 10:38 pm, Keith H Duggar <dug... (AT) alum (DOT) mit.edu> wrote:

Quote:

On Apr 13, 3:42 am, David BL <davi... (AT) iinet (DOT) 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.

#17

On Apr 12, 1:13 am, David BL <davi... (AT) iinet (DOT) net.au> wrote:

Quote:

If
this is how the RM is meant to fit into the picture

You have a lot of confusions and misunderstandings about
FOPL, relations, RVAs, Prolog and programming abstraction.

If you would properly write out the simplest database
some of this would begin to become apparent to you.

What are the names of your relation variables and constants?
What is the characteristic predicate
(parameterized statement about the world) for each?
What is the formal wff for each? Why?
What are the attributes for each? Why?
What is your (example) query relation expression?
What is the characteristic predicate of its result? Why?
What are the (example) values of your relation variables?
What statement does each make about the world? Why?
What statement does the database make about the world? Why?
What is the value of your query relation expression? Why?
What statement does this value make about the world
in the context of this query relation expression? Why?
What statement does a query result make about the world
regardless of its query relation expression? Why?

The most important things to understand are that:
1. each relation expression corresponds to a certain wff and
2. equivalent relation expressions correspond to equivalent wffs
The relational algebra is just another syntax for FOPL.
(So they can't possibly be at odds.)

The meaning of an RVA or a TVA, as with any attribute,
is whatever the predicate of its containing relation gives it.
Any attribute value could denote an abstract value or just itself.
The only thing special about an RVA is that it is relation-valued.
Usually it denotes a set of tuples that satisfy a predicate
(the usual role of a relation value in database management).
The only thing special about a TVA is that it is tuple-valued.
Usually it denotes either a tuple that satisfies a predicate
(the usual role of a tuple value in database management)
or to denote a publicly complex/structured value.
Other idioms complicate querying.

philip

#18

On Apr 12, 1:13 am, David BL <davi... (AT) iinet (DOT) net.au> wrote:

Quote:

If
this is how the RM is meant to fit into the picture

You have a lot of confusions and misunderstandings about
FOPL, relations, RVAs, Prolog and programming abstraction.

If you would properly write out the simplest database
some of this would begin to become apparent to you.

What are the names of your relation variables and constants?
What is the characteristic predicate
(parameterized statement about the world) for each?
What is the formal wff for each? Why?
What are the attributes for each? Why?
What is your (example) query relation expression?
What is the characteristic predicate of its result? Why?
What are the (example) values of your relation variables?
What statement does each make about the world? Why?
What statement does the database make about the world? Why?
What is the value of your query relation expression? Why?
What statement does this value make about the world
in the context of this query relation expression? Why?
What statement does a query result make about the world
regardless of its query relation expression? Why?

The most important things to understand are that:
1. each relation expression corresponds to a certain wff and
2. equivalent relation expressions correspond to equivalent wffs
The relational algebra is just another syntax for FOPL.
(So they can't possibly be at odds.)

The meaning of an RVA or a TVA, as with any attribute,
is whatever the predicate of its containing relation gives it.
Any attribute value could denote an abstract value or just itself.
The only thing special about an RVA is that it is relation-valued.
Usually it denotes a set of tuples that satisfy a predicate
(the usual role of a relation value in database management).
The only thing special about a TVA is that it is tuple-valued.
Usually it denotes either a tuple that satisfies a predicate
(the usual role of a tuple value in database management)
or it denotes a publicly complex/structured value.
Other idioms complicate querying.

philip

#19

On Apr 15, 5:01 am, com... (AT) hotmail (DOT) com wrote:

Quote:

On Apr 12, 1:13 am, David BL <davi... (AT) iinet (DOT) net.au> wrote:

If
this is how the RM is meant to fit into the picture

You have a lot of confusions and misunderstandings about
FOPL, relations, RVAs, Prolog and programming abstraction.

If you would properly write out the simplest database
some of this would begin to become apparent to you.

What are the names of your relation variables and constants?
What is the characteristic predicate
(parameterized statement about the world) for each?
What is the formal wff for each? Why?
What are the attributes for each? Why?
What is your (example) query relation expression?
What is the characteristic predicate of its result? Why?
What are the (example) values of your relation variables?
What statement does each make about the world? Why?
What statement does the database make about the world? Why?
What is the value of your query relation expression? Why?
What statement does this value make about the world
in the context of this query relation expression? Why?
What statement does a query result make about the world
regardless of its query relation expression? Why?

The most important things to understand are that:
1. each relation expression corresponds to a certain wff and
2. equivalent relation expressions correspond to equivalent wffs
The relational algebra is just another syntax for FOPL.
(So they can't possibly be at odds.)

You are merely talking about the correspondence between formulae in
FOL versus expressions in the RA. E.g.

RA: project((R1 join R2) union R3, {X})
FOL: exists y,z such that (P1(x,y) /\ P2(y,z)) \/ P3(x,y,z)

R1,R2,R3 are relvar names. X is an attribute name. P1,P2,P3 are
predicate symbols. x,y,z are variables.

My original post concerned *terms* in FOL which are not formulae. If
you disagree with something I said then why don't you discuss that
rather than something unrelated?

Quote:

The meaning of an RVA or a TVA, as with any attribute,
is whatever the predicate of its containing relation gives it.
Any attribute value could denote an abstract value or just itself.

In a formal semantic on a FOL there is a given "domain of discourse"
which is the set (of "values") over which quantification is deemed to
take place. Each FOL term represents a "value" which is a single
element of this set. The interpretation of an n-ary predicate symbol
is the indicator function of some given set of n-tuples of elements of
the domain of discourse.

A formal semantic says nothing about the "meaning" of the counterpart
to an attribute (which in FOL corresponds to a variable on which a
predicate is parameterised). I challenge you to formalise what you
said above. What is a formal definition of the "meaning" of an
attribute? What exactly does it mean for an attribute value to
"denote" something? To be frank you don't appear to know what
you're talking about.

It appears you might claim for example that a predicate parameterised
by a circle value "really means" a predicate parameterised by a square
value (say of the same area as the circle), thereby concluding that
the circle in fact "denotes" a square. That's just silly.

[snip]

#20

David BL wrote:

Quote:

On Apr 15, 5:01 am, com... (AT) hotmail (DOT) com wrote:
....
The relational algebra is just another syntax for FOPL.
(So they can't possibly be at odds.)

You are merely talking about the correspondence between formulae in
FOL versus expressions in the RA. E.g.

RA: project((R1 join R2) union R3, {X})
FOL: exists y,z such that (P1(x,y) /\ P2(y,z)) \/ P3(x,y,z)

R1,R2,R3 are relvar names. X is an attribute name. P1,P2,P3 are
predicate symbols. x,y,z are variables.
...

Regarding precision, as far as I know, relvars are pointers and the
several relational algebras do not manipulate pointers.

(To me this means that an implementation of such an algebra doesn't
require relvars.)