I recommend the article http://en.wikipedia.org/wiki/First-order_logic
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.

On Apr 12, 1:13 am, David BL <davi... (AT) iinet (DOT) net.au> wrote:
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.

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.

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.

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".

What does "become functions" mean? Anyhow, interpretation is
orthogonal and therefore irrelevant to both FOL and RM.

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.

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.

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.

Yes exactly, just as in FOL interpretation is orthogonal.

Non-sequitur. That something defines no concept of A does not
imply that "A has already taken place".

Correct. Just as a FOL clause "encodes nothing other than itself".
Interpretation is left to some other formal semantics system.

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

On Apr 12, 2:37 pm, Keith H Duggar <dug... (AT) alum (DOT) mit.edu> wrote:
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).


I completely agree and didn't mean to imply otherwise.


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).


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.


Yes the word "become" was very informal. In the wiki article it
states rather informally "the interpretation of a function symbol is a
function".


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'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?



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.

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.


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

David BL wrote:
....
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.

David BL wrote:


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.

On Apr 12, 7:09 am, David BL <davi... (AT) iinet (DOT) net.au> wrote:
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?

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.

Ok.

Got it.

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.

relational algebraic expressions or "views" of which relations
with RVAs are a subset.

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

Keith H Duggar wrote:

Are you conflating physical and conceptual?


<snip>

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


I think the correct answer in both cases is "sometimes".

On Apr 12, 1:51 pm, Bob Badour <bbad... (AT) pei (DOT) sympatico.ca> wrote:
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

On 12 avr, 16:35, paul c <toledobythe... (AT) oohay (DOT) ac> wrote:

Within D&D, I sometime perceive RVA's as a half-baked attempt to
formalize complex types.

But that is just me.

Cimode wrote:
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.