Expressions versus the value they represent
David BL
when reading this post.
In FOL the expression circle(point(0,0),1) is called a /term/. It is
actually a ground term because there are no variables. It is NOT a
circle! circle and point are /function symbols/ of arity 2. 0 and 1
are function symbols of arity 0. Terms can nest (e.g. 0, 1 and
point(0,0) are all terms).
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.
In FOL one distinguishes between a term and what it encodes under an /
interpretation/. Under an interpretation function symbols become
functions. For example, let circle(c,r) be a function that maps point
c and number r to a circle centred at c with radius r. i.e.
circle(c,r) = { (x,y) in RxR | (x-c.x)^2 + (y-c.y)^2) = r^2 }
Terms can be seen as a way to encode values that would otherwise be
impossible to directly represent on a computer. E.g. a circle is
uncountably infinite.
What interests me here is the question of whether or not it is
appropriate for a formalism underlying database theory to distinguish
between terms and the abstract values they encode under
interpretation. At stake is the ability to express ideas such as the
following clause in Prolog, which states for example that the term 3+4
should be simplified to the term 7:
simplify(X,Y) :- Y is simplified version of X
simplify( plus(num(X), num(Y)), num(X+Y) ).
Obviously one cannot satisfactorily manipulate expressions if they are
only seen for the abstract values that they encode.
I note that a D&D /selector/ for type CIRCLE is like a function that
returns an abstract circle value (e.g. already interpreted and ready
to be stuck into a relation). It seems implicit with the RM that
there is no concept of interpretation (or putting it another way,
interpretation has already taken place). A relation or tuple value
encodes nothing other than itself. So to for the attribute values of
any given tuple.
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.
The FOL distinguishes between function symbols and predicate symbols.
Under interpretation a predicate symbol becomes a boolean valued
function, which is the indicator function of some given relation. If
this is how the RM is meant to fit into the picture then it seems
inappropriate to use relations to somehow encode the values that are
normally encoded by FOL terms.
Keith H Duggar
> I recommend the articlehttp://en.wikipedia.org/wiki/First-order_logic
> when reading this post.
First a general point about communication. When one is trying to
write a post with such an "air" of formalism and precision, then
it is especially important to hold to accepted formal vocabulary.
Otherwise we end up with a jumble of formal sounding arguments
mixed with just enough ambiguous "everyday-man" language to sow
confusion and instantiate the Principle of Incoherence.
For example, below we find phrases such as "/returns/ an abstract
circle", "/become/ functions", "/play around with/", "only /seen/
for abstract values", etc (where I've highlighted the particular
words in question) which at worst are entirely meaningless and
incoherent and at best ambiguous.
> In FOL the expression circle(point(0,0),1) is called a /term/. It is
> actually a ground term because there are no variables. It is NOT a
> circle! circle and point are /function symbols/ of arity 2. 0 and 1
> are function symbols of arity 0. Terms can nest (e.g. 0, 1 and
> point(0,0) are all terms).
That is a contradiction. You claim the term circle(...) is "NOT a
circle!" then immediately claim that a "circle [is a] /function
symbol". Note that in both claims you used the 6 letters "circle".
As far as FOL is concerned "circle" is a symbol nothing more and
nothing less and there a "circle" IS a "circle". Interpretation is
orthogonal to FOL and therefore so is the meta-knowledge from which
you derive this truth that "circle is NOT a circle!". Exclaiming
that is meaningless in the context of FOL.
> 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.
> In FOL one distinguishes between a term and what it encodes under an /
> interpretation/.
No it's more than that. Interpretation is /orthogonal/ to FOL. The
extent to which FOL distinguishes is only to state that "FOL says
nothing about the business of interpretation".
> Under an interpretation function symbols become
> functions. For example, let circle(c,r) be a function that maps point
> c and number r to a circle centred at c with radius r. i.e.
>
> circle(c,r) = { (x,y) in RxR | (x-c.x)^2 + (y-c.y)^2) = r^2 }
What does "become functions" mean? Anyhow, interpretation is
orthogonal and therefore irrelevant to both FOL and RM.
> Terms can be seen as a way to encode values that would otherwise be
> impossible to directly represent on a computer. E.g. a circle is
> uncountably infinite.
That would be conflating the logical and physical layers, a problem
we've all seen far too many times. Yes, terms can be thought of as
having a type and some extension. However, that extension need never
be enumerated, nor have it's structure defined, nor be represented
on a computer, nor anything else stated about it (besides existence)
apart from any type definitions and other axioms. At least as far as
/theory/ goes. Creating a computerized or imagined implementation is
a separate physical concern.
> What interests me here is the question of whether or not it is
> appropriate for a formalism underlying database theory to distinguish
> between terms and the abstract values they encode under
> interpretation. At stake is the ability to express ideas such as the
> following clause in Prolog, which states for example that the term 3+4
> should be simplified to the term 7:
>
> simplify(X,Y) :- Y is simplified version of X
> simplify( plus(num(X), num(Y)), num(X+Y) ).
>
> Obviously one cannot satisfactorily manipulate expressions if they are
> only seen for the abstract values that they encode.
Well fortunately the RM does not "see" them as abstract values.
It "sees" them in exactly the same when they are "seen" in FOL,
as terms, as expressions, they may or may not have a type. So,
we are in luck: the RM does not in any way limit the expression
of such clauses.
> I note that a D&D /selector/ for type CIRCLE is like a function that
> returns an abstract circle value (e.g. already interpreted and ready
> to be stuck into a relation).
A selector does not "return" a value. It /denotes/ or /selects/
a value. And again this value is not interpreted in the RM because
interpretation is orthogonal to both FOL and RM.
> It seems implicit with the RM that there is no concept of interpretation
Yes exactly, just as in FOL interpretation is orthogonal.
> (or putting it another way, interpretation has already taken place).
Non-sequitur. That something defines no concept of A does not
imply that "A has already taken place".
> A relation or tuple value encodes nothing other than itself. So to
> for the attribute values of any given tuple.
Correct. Just as a FOL clause "encodes nothing other than itself".
Interpretation is left to some other formal semantics system.
> 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.
>
> The FOL distinguishes between function symbols and predicate symbols.
> Under interpretation a predicate symbol becomes a boolean valued
> function, which is the indicator function of some given relation. If
> this is how the RM is meant to fit into the picture then it seems
> inappropriate to use relations to somehow encode the values that are
> normally encoded by FOL terms.
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.
KHD
David BL
> On Apr 12, 1:13 am, David BL <davi...@iinet.net.au> wrote:
>
> > I recommend the articlehttp://en.wikipedia.org/wiki/First-order_logic
> > when reading this post.
>
> First a general point about communication. When one is trying to
> write a post with such an "air" of formalism and precision, then
> it is especially important to hold to accepted formal vocabulary.
> Otherwise we end up with a jumble of formal sounding arguments
> mixed with just enough ambiguous "everyday-man" language to sow
> confusion and instantiate the Principle of Incoherence.
>
> For example, below we find phrases such as "/returns/ an abstract
> circle", "/become/ functions", "/play around with/", "only /seen/
> for abstract values", etc (where I've highlighted the particular
> words in question) which at worst are entirely meaningless and
> incoherent and at best ambiguous.
>
> > In FOL the expression circle(point(0,0),1) is called a /term/. It is
> > actually a ground term because there are no variables. It is NOT a
> > circle! circle and point are /function symbols/ of arity 2. 0 and 1
> > are function symbols of arity 0. Terms can nest (e.g. 0, 1 and
> > point(0,0) are all terms).
>
> That is a contradiction. You claim the term circle(...) is "NOT a
> circle!" then immediately claim that a "circle [is a] /function
> symbol". Note that in both claims you used the 6 letters "circle".
It's not a contradiction if you allow for the word "circle" to be
overloaded (which I thought was obvious). I should have used
different names for the symbols to avoid confusion. E.g. I could have
said:
In FOL the expression c(p(0,0),1) is called a /term/.
It is actually a ground term because there are no
variables. It is NOT a circle! c and p are
/function symbols/ of arity 2. 0 and 1 are function
symbols of arity 0. Terms can nest (e.g. 0, 1 and p(0,0)
are all terms).
> As far as FOL is concerned "circle" is a symbol nothing more and
> nothing less and there a "circle" IS a "circle". Interpretation is
> orthogonal to FOL and therefore so is the meta-knowledge from which
> you derive this truth that "circle is NOT a circle!". Exclaiming
> that is meaningless in the context of FOL.
I completely agree and didn't mean to imply otherwise.
> > 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).
> > In FOL one distinguishes between a term and what it encodes under an /
> > interpretation/.
>
> No it's more than that. Interpretation is /orthogonal/ to FOL. The
> extent to which FOL distinguishes is only to state that "FOL says
> nothing about the business of interpretation".
I think you made a valid point there. The wiki article suggests
interpretation falls under "formal semantics". You are suggesting, I
think correctly, that a formal semantics doesn't come under the scope
of FOL.
> > Under an interpretation function symbols become
> > functions. For example, let circle(c,r) be a function that maps point
> > c and number r to a circle centred at c with radius r. i.e.
>
> > circle(c,r) = { (x,y) in RxR | (x-c.x)^2 + (y-c.y)^2) = r^2 }
>
> What does "become functions" mean?
Yes the word "become" was very informal. In the wiki article it
states rather informally "the interpretation of a function symbol is a
function".
> 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.
Perhaps it would be worth discussing whether that is a fundamental
requirement in database theory? I consider "data" to mean "encoded
value".
I'm not sure what you mean. What are you suggesting is the equivalent
of nested terms/expressions in the RM? I assume you mean relation or
tuple valued attributes. If so I would say we are in luck in one
sense but badly out of luck in another.
As I think you suggest, we are in luck because it is possible to
manipulate the nested "expressions" transparently without any
limitations.
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?
> > I note that a D&D /selector/ for type CIRCLE is like a function that
> > returns an abstract circle value (e.g. already interpreted and ready
> > to be stuck into a relation).
>
> A selector does not "return" a value. It /denotes/ or /selects/
> a value.
I'm not sure what your point is. I agree that saying a function
"returns" a value is a reasonably common but rather poor
colloquialism. Or are you claiming that a selector is not a
function?
> And again this value is not interpreted in the RM because
> interpretation is orthogonal to both FOL and RM.
>
> > It seems implicit with the RM that there is no concept of interpretation
>
> Yes exactly, just as in FOL interpretation is orthogonal.
>
> > (or putting it another way, interpretation has already taken place).
>
> Non-sequitur. That something defines no concept of A does not
> imply that "A has already taken place".
I was being metaphorical. Selectors are typically used to help
specify relations or to insert tuples into relvars, and selectors are
able to select abstract values like circles. Selectors are analogous
to FOL ground terms "after" an interpretation. My somewhat terse
remark is associated with the observation that attribute values aren't
like FOL terms that are "waiting" to be interpreted.
> > A relation or tuple value encodes nothing other than itself. So to
> > for the attribute values of any given tuple.
>
> Correct. Just as a FOL clause "encodes nothing other than itself".
> Interpretation is left to some other formal semantics system.
Actually I was limiting my use of the word "encode" to mean
interpretation. The concept of an interpretation on FOL terms is very
common. Whether or not "FOL" technically encompasses a formal
semantics doesn't change that fact. Not does it change the fact that
there isn't a convention for interpreting a relation or tuple as
something other than itself.
> > 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.
>
> > The FOL distinguishes between function symbols and predicate symbols.
> > Under interpretation a predicate symbol becomes a boolean valued
> > function, which is the indicator function of some given relation. If
> > this is how the RM is meant to fit into the picture then it seems
> > inappropriate to use relations to somehow encode the values that are
> > normally encoded by FOL terms.
>
> 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.
paul c
...
> 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'.
They seem reasonable to me as far as they go. That doesn't mean I like
them.
Bob Badour
> On Apr 12, 2:37 pm, Keith H Duggar <dug...@alum.mit.edu> wrote:
>
>>On Apr 12, 1:13 am, David BL <davi...@iinet.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.
Keith H Duggar
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?
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. 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?
> > > In FOL the expression circle(point(0,0),1) is called a /term/. It is
> > > actually a ground term because there are no variables. It is NOT a
> > > circle! circle and point are /function symbols/ of arity 2. 0 and 1
> > > are function symbols of arity 0. Terms can nest (e.g. 0, 1 and
> > > point(0,0) are all terms).
>
> > That is a contradiction. You claim the term circle(...) is "NOT a
> > circle!" then immediately claim that a "circle [is a] /function
> > symbol". Note that in both claims you used the 6 letters "circle".
>
> It's not a contradiction if you allow for the word "circle" to be
> overloaded (which I thought was obvious). I should have used
> different names for the symbols to avoid confusion. E.g. I could have
> said:
>
> In FOL the expression c(p(0,0),1) is called a /term/.
> It is actually a ground term because there are no
> variables. It is NOT a circle! c and p are
> /function symbols/ of arity 2. 0 and 1 are function
> symbols of arity 0. Terms can nest (e.g. 0, 1 and p(0,0)
> are all terms).
Agreed. However, that is an important clarification because
now I may clearly ask that you define "circle". Mostly likely
in a FOL-only discussion it would remain undefined as just a
symbol. But, as is now clear, you are aiming instead at some,
as yet undefined, interpretation. That's what was not clear
to me in the original post.
> > > 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).
Ok.
> > 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".
Hmm ... interesting question. I'm guessing, and this truly is
a guess, that in the larger context of "database theory" the
answer is yes. In the smaller context of "relational model"
the answer is no. I hope one of the "regulars" will correct
and expound on this.
> > > What interests me here is the question of whether or not it is
> > > appropriate for a formalism underlying database theory to distinguish
> > > between terms and the abstract values they encode under
> > > interpretation. At stake is the ability to express ideas such as the
> > > following clause in Prolog, which states for example that the term 3+4
> > > should be simplified to the term 7:
>
> > > simplify(X,Y) :- Y is simplified version of X
> > > simplify( plus(num(X), num(Y)), num(X+Y) ).
>
> > > Obviously one cannot satisfactorily manipulate expressions if they are
> > > only seen for the abstract values that they encode.
>
> > Well fortunately the RM does not "see" them as abstract values.
> > It "sees" them in exactly the same when they are "seen" in FOL,
> > as terms, as expressions, they may or may not have a type. So,
> > we are in luck: the RM does not in any way limit the expression
> > of such clauses.
>
> I'm not sure what you mean. What are you suggesting is the equivalent
> of nested terms/expressions in the RM? I assume you mean relation or
> tuple valued attributes.
relational algebraic expressions or "views" of which relations
with RVAs are a subset.
> If so I would say we are in luck in one
> sense but badly out of luck in another.
>
> As I think you suggest, we are in luck because it is possible to
> manipulate the nested "expressions" transparently without any
> limitations.
>
> 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?
KHD
Bob Badour
> On Apr 12, 7:09 am, David BL <davi...@iinet.net.au> wrote:
>
>>On Apr 12, 2:37 pm, Keith H Duggar <dug...@alum.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?
>
> 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. 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?
Are you conflating physical and conceptual?
<snip>
>>>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. The data
might encode information originating in a different form, or it may
originate in a suitable representation.
Database theory at the conceptual and logical levels of discourse
requires no computer. While the primary application of database theory
is to record information on physical devices and while the vast majority
of such devices involve digital electronics, those devices need have
nothing to do with digital electronics. e.g. a card catalog
> Hmm ... interesting question. I'm guessing, and this truly is
> a guess, that in the larger context of "database theory" the
> answer is yes. In the smaller context of "relational model"
> the answer is no. I hope one of the "regulars" will correct
> and expound on this.
I think the correct answer in both cases is "sometimes".
Keith H Duggar
> Keith H Duggar wrote:
> > On Apr 12, 7:09 am, David BL <davi...@iinet.net.au> wrote:
>
> >>On Apr 12, 2:37 pm, Keith H Duggar <dug...@alum.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?
>
> > 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. 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?
>
> Are you conflating physical and conceptual?
Maybe. I don't know.
In my thinking from the perspective of the logical layer both
the conceptual and physical layers are just "models" ie valid
interpretations for the logical layer.
Of course we imagine some "precedence" among them in that we
often say the logical layer "implements" the conceptual layer
and the physical layer "implements" the logical layer. But,
this is just an artificial albeit useful ordering of what are
flat role relationships.
Anyhow, it seemed to me that DBL was focussing on a layer used
to "implement" certain functions such as equality etc and that
layer is not necessarily identical to the conceptual layer.
For example, in the DirectedGraph example I posed it may be the
case that the concept domain is optimizing airline schedules, or
power distribution, etc and as part of implementing those concepts
we choose a relation that has DirectedGraph valued attributes.
And we find that isomorphism is the notion of equality we need
to implement the functions we need to solve the problems we are
interested in.
So in that scenario I would think the "conceptual" layer is the
airline schedules or power distribution, the logical layer is the
various relations such as the one having DirectedGraph, and the
physical layer are the bits and bytes and/or imagined sets (for
example integers) and algorithms used to implement the various
functions we need.
But, from the perspective or logic, both the airline schedules and
the bits and bytes or sets are "interpretations" or "models" of
the logical layer.
Anyhow, that's just how I was thinking of the layers in DBLs
context. Please let me know if and how this is far off the
accepted definitions.
Thanks!
KHD
Cimode
Within D&D, I sometime perceive RVA's as a half-baked attempt to
formalize complex types.
But that is just me.
paul c
As for me, I don't have the impression that Date touts RVA's, it's just
that a relation definition being a type definition in the D&D approach,
they are a consequence and so they are a possibility. Whether they are
desireable is another question.
David BL
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.
David BL
> >>>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?
David BL
> On Apr 12, 7:09 am, David BL <davi...@iinet.net.au> wrote:
>
> > On Apr 12, 2:37 pm, Keith H Duggar <dug...@alum.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.
> 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.
> 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.
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.
David BL
> 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.
Keith H Duggar
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
David BL
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.
com...@hotmail.com
> 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
David BL
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?
> 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]
paul c
>> 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.)
David BL
> David BL wrote:
> > On Apr 15, 5:01 am, com...@hotmail.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.
Perhaps we should say that R1,R2,R3 are relation symbols within the RA
expression, and under an interpretation these symbols are given
relation values. In that context, it appears that an RA expression is
treated just like an FOL term.
Indeed to highlight the potential confusion consider this. One could
write the following formula in a FOL with equality:
for all R1, R2, R1 join R2 = R2 join R1
and in that formula R1,R2 are (bound) FOL variables and the FOL terms
on the two sides of '=' are RA expressions. So even though on the one
hand we often think of a correspondence between RA expressions and FOL
formulas, within this FOL formula they are instead FOL terms. One
presumably might refer to R1 and R2 as "relation variables".
So it seems that "relation variable" can be overloaded for two
distinct purposes. When I see "relvar" I assume there is a physical
database that holds particular named relation values at each moment in
time. In that case we have a concept of assignable relvars accessible
by some imperative language. The language is necessarily at least
partly imperative because an assignment statement is by definition
imperative.
I'm not sure what you mean by saying that a relvar is a pointer. What
does it point at? Or do you mean a relvar name is like a pointer that
points at an assignable variable within a physical database?
> (To me this means that an implementation of such an algebra doesn't
> require relvars.)
Yes by treating relation names as either FOL function symbols or FOL
variables and by treating RA expressions as FOL terms.
paul c
...
> I'm not sure what you mean by saying that a relvar is a pointer. What
> does it point at? Or do you mean a relvar name is like a pointer that
> points at an assignable variable within a physical database?
Nor I you. As I said, a relvar is a pointer, so not it's confusing to
say it's 'like' one. I thought it 'pointed' to a value, maybe there is
some cultural language nuance that I'm not able to comprehend that
somehow makes a difference in the eyes of some beholder or othe. Maybe
Bob B can explain the difference between a relational pointer and some
other kind of pointer but I would have thought the difference was patent
regardless of context. (I think 'assignment' is a difficult notion but
am glad you mentioned it.) Personally, for practial reasons if none
other, I would prefer to think of a pointer as being a pointer,
regardless of cultural context.
David BL
Below 'variable' is restricted to something that can be accessed by
imperative statements, and not to be confused with a FOL variable.
I don't say a variable points at a value. I say a variable *holds* a
value. I restrict my usage of the word "pointer" to mean a *value*
that represents an address or you could say an identifier for a
variable. So a pointer points at a variable, not directly at a
value.
E.g. In C++
int x = 10;
int* p = &x;
x is not a pointer. x is a variable that holds the value 10. p is a
pointer variable that holds a pointer value. The pointer value points
at the variable named x. There is no concept of a pointer value that
points at the value 10. I don't understand what that could mean.
Note that C++ outlaws the expression &10.
paul c
...
> Below 'variable' is restricted to something that can be accessed by
> imperative statements, and not to be confused with a FOL variable.
>
> I don't say a variable points at a value. I say a variable *holds* a
> value. I restrict my usage of the word "pointer" to mean a *value*
> that represents an address or you could say an identifier for a
> variable. So a pointer points at a variable, not directly at a
> value.
>
> E.g. In C++
>
> int x = 10;
> int* p = &x;
>
> x is not a pointer. x is a variable that holds the value 10. p is a
> pointer variable that holds a pointer value. The pointer value points
> at the variable named x. There is no concept of a pointer value that
> points at the value 10. I don't understand what that could mean.
> Note that C++ outlaws the expression &10.
>
What has C++ got to do with any algebraic language? What does
assignment have to do with any algebraic language?
(Regarding C++ I would say a more apt comparison with algebra symbols
would be "const int x = 10;").
David BL
Nothing, as also "pointer" has nothing to do with any algebraic
language.
My interpretation of the conversation is:
1) As far as RA being a pure algebra is concerned I incorrectly stated
that R1,R2,R3 were relvar names. I acknowledged that in a subsequent
post where I instead suggested R1,R2,R3 represent FOL function symbols
or else FOL variables. In the case that they are function symbols, it
can be the case that the intention is for them to be given the current
values of the physical database relvars of the same name under
interpretation.
2) You corrected me, but in doing so incorrectly claimed that relvars
are pointers, when really they are just assignable variables that hold
relation values in the context of an imperative language.
3) I proceeded to talk about what "pointer" means (a value that
identifies a variable in the context of an imperative language).
4) You appear to think incorrectly that I'm talking about pointers in
the context of an algebra.
> (Regarding C++ I would say a more apt comparison with algebra symbols
> would be "const int x = 10;").
I wasn't making any comparison with algebra symbols.
Reinier Post
>E.g. In C++
>
> int x = 10;
> int* p = &x;
>
>x is not a pointer. x is a variable that holds the value 10. p is a
>pointer variable that holds a pointer value.
Good point. (You must be a good pointer.)
Meanwhile, in Algol 68,
INT x := 10
is a shorthand for
REF INT x = LOC INT; x := 10
i.e. a variable is of type reference to integer (Algol 68 doesn't use
the term 'pointer'.) This is because
INT x = 10
defines a *constant* x with the value 10. (The original C doesn't have
constants.) So Algol 68 essentially agrees with paul's terminology,
except that it uses 'reference' for 'pointer'.
--
Reinier
paul c
Yes, if you change the terms of reference, I'd bet you could always turn
the meaning of a term into something that is contrary on some surface or
other. It always seemed to me that a C "variable" had effectively the
same result as a pointer did, perhaps because in my case the programming
background was assembler, so even when I look at C code, I see the
registers being loaded, either by an interpreter or effectively by a
compiler. If I had started with C, maybe my life would have been more
complicated because instead of registers I'd have a whole bunch of other
concepts to master, such as "holding a value"! Can't prove it but I
suspect most problems of this kind will be solved when enough
generations pass, even if others arise.
Neville Dempsey
> David BL wrote:
> >E.g. In C++
> > int x = 10;
> > int* p = &x;
In C: There is the necessity of sprinkling "salt" and "pepper" over C
code in the form of the "*" and "&" operators in order to get the
dereferencing "just right". See code specimens included below for a
comparison....
Algol68 has endeavored to minimise the condiments in the actual code,
and - typically - automatically dereferences "pointers" to the actual
data.
But A68 still needs some condiments, eg Compare the specimen code
extracts where a "pointer" is dereferenced for assignment.
C: ***r = 666; /* C needs to be instructed how to
dereference to the get the right outcome. */
A68: REF INT(r):=666; ¢ In this case Algol68 needs to be told what
outcome "type" is required for the LHS ¢
[ Imagine doing this in C: *(int*)r = 666; /* a big contrast with no
warning msg! */ ]
Ironically GCC actually knows what type is required and warns the
coder if the "***r=10" is incorrectly coded as "r=10". But things can
get spicy in C if there is not enough salt. :-) eg:
> is.c:9: warning: assignment makes pointer from integer without a cast;
THEN "Segmentation fault" when binary is run.
In A68, if the "REF INT(" condiment is missing on the assignment then
the coder would get the following "type syntax error" message, eg:
r := 666;
> 8: INT cannot be coerced to REF REF REF INT in a strong-unit
Code specimens with output:
code: - - - - 8>< - - - - - - - -
$ cat is.c
#include <stdio.h>
main(){
int x;
int *p = &x;
int **q = &p;
int ***r = &q;
x=10;
***r = 666;
if(*p == x ) printf("*p == x\n");
if(**q == x ) printf("**q == x\n");
if(***r == x ) printf("***r == x\n");
if(**r == &x ) printf("**r is x\n");
}
output: - - - - 8>< - - - - - - - -
$ gcc is.c -o is; ./is
*p == x
**q == x
***r == x
**r is x
code: - - - - 8>< - - - - - - - -
$ cat ./is.a68
main:(
INT x;
REF INT p := x;
REF REF INT q := p;
REF REF REF INT r := q;
x:=10; ¢ OK ¢
REF INT(r) := 666; ¢ dereference required ¢
IF p = x THEN printf($"p = x"l$) FI;
IF q = x THEN printf($"q = x"l$) FI;
IF r = x THEN printf($"r = x"l$) FI;
IF r IS x THEN printf($"r IS x"l$) FI
)
output: - - - - 8>< - - - - - - - -
$ a68g ./is.a68
p = x
q = x
r = x
r IS x
--
To download Linux's Algol68 Compiler, Interpreter & Runtime:
* http://sourceforge.net/projects/algol68