On page 116 of An Introduction to Database Systems (8th edition) Chris
Date provides the following example:

TYPE POINT
POSSREP CARTESIAN { X RATIONAL, Y RATIONAL }
POSSREP POLAR { R RATIONAL, THETA RATIONAL };

A footnote on that page states "Tutorial D uses the more accurate
RATIONAL over the more familiar REAL".

I find this quite confusing, hence the following questions:

1) In the opening paragraphs of section 5.3 which is where POSSREPs
are described, the word 'representation' is often qualified by
'physical'. Is it correct to assume that a POSSREP is indeed a
physical representation (and has nothing to do with declaring "logical
representations" which is a term I've seen mentioned a few times on
this news group)?

2) Is it reasonable for me to assume a physical representation of type
T means some unambiguously defined method for encoding values of type
T on some physical medium?

3) Is it correct that a POSSREP typically doesn't unambiguously define
a method for encoding values of type T on some physical medium?

4) Consider a POINT value is encoded in computer memory using a '\0'
terminated ASCII string such as "(1.34,-6.2)", and must be parsed
according to some well defined grammar in order to retrieve the x,y
coordinates. Does this qualify as a CARTESIAN representation?

5) Is it correct to say that in Tutorial D types are sometimes defined
in terms of possreps?

6) Date states that types are by definition abstract (i.e. type means
Abstract Data Type). Can I assume by abstract he is referring to pure
mathematical abstractions which are completely divorced from real
world objects? If that is the case, is it not strange to define the
abstract (like POINT) in terms of possible physical representations
(like CARTESIAN or POLAR)?

7) Is it true that the DDL doesn't separate out the abstractions from
the physical representations, and therefore it is not possible to read
the abstractions without being exposed to physical representation
details? Is it true that software developers cannot extend or modify
the physical representations without updating the definitions of the
abstractions?

8) In that same footnote mentioned above it is stated RATIONAL might
be a built-in type with more than one declared possible
representation. Can I assume RATIONAL is necessarily a type, and not
a possrep? Are possreps allowed to reference other possreps? I would
actually have thought it only makes sense to define a possrep in terms
of other possreps. E.g. in an implementation language like C we may
write

struct Cartesian { float x,y; };

In this case, on a given platform, a particular representation of a
geometrical point is unambiguously defined in terms of particular
representations of numbers. If RATIONAL is a type what does it mean
to define a physical representation CARTESIAN in terms of a pure
abstraction RATIONAL? Does this mean Date thinks of POSSREPS as
abstractions?

9) Is it correct to assume that in this usage of RATIONAL it is not
meant to be associated with a TYPE/POSSREP which has the purpose of
representing rationals exactly using a pair of "big integers" as long
as memory is not exhausted, since such a type would not normally
support the operators such as SQRT, SIN, COS and ARCTAN which appear
on pages 117,118 and typically return irrationals?

10) Is Date probably thinking that a floating point representation is
in practise used for RATIONAL?

11) Does the footnote imply Date assumes that floating point numbers
should be regarded as representing certain rationals exactly and only
thinks of the operators as approximate?

12) Am I correct in thinking that Date should instead think of floats
as an approximate representation of the reals? My reasons for
thinking this are:

a) since only certain rationals can be represented exactly, we are
forced
to represent most numbers only approximately.

b) given that the operations are typically approximate, the results
of
calculation are typically approximate. Therefore the floats
themselves are an approximation.

c) the abstract operators such as exp,log,sqrt,sin,cos,tan are
unary
operators on the reals, so it makes little sense to implement
them for
floating point numbers and yet regard floats as approximations
to
rationals.

13) Is it appropriate for assumptions about types employed in POSSREP
declarations to be visible in the signatures of the operators at the
logical level of discourse? For example, that the return type of
THE_X is RATIONAL:

OPERATOR THE_X ( P POINT ) RETURNS RATIONAL;

14) Is there a requirement that each possrep be complete (meaning it
can represent all possible values of the given type)? I note that on
page 606 it states "Part of the definition of any given type is a
specification of the set of all legal values of that type". Is it
assumed this specification normally comes implicitly from one or more
possreps, and is this a reason that on page 115 it is stated "... we
do require that values of type T have at least one possible
representation"?

15) Does Date assume that the set of legal values of type POINT is
well defined? What does that mean if floats are used, thought of as
representing certain rationals exactly but exact conversions between
the two representations don't generally exist?

16) Does Date outlaw types which are uncountably infinite (because
there is no representation with a finite encoding for every value)?

17) Why are only some operators called "selectors"? I would have
thought this distinction only arises from physical implementation
concerns. Is it not true that at an abstract level any operator that
returns values of type T can be regarded as a means of selecting
values of type T?

18) On page 606 it is stated "The physical representation of such
values is always hidden from the user" and in the same paragraph "each
type has at least one possible representation that is explicitly
exposed to the user". How does one reconcile these apparently
contradictory statements? What is Date saying exactly?

19) Can the definition of nonscalar be formalised? What is meant
precisely by "user visible, directly accessible components"? Why
isn't a POINT a nonscalar given that user access is provided to
X,Y,R,THETA through operators such as THE_X? On the topic of
physical representations Date states "... they can certainly have
components - but ... any such components will be hidden from the
user". What does he mean by hidden? Since tuple and relation types
have physical representations why doesn't Date's latter statement
apply to them as well?

On 2011-05-26, David BL <davidbl (AT) iinet (DOT) net.au> wrote:
No. A possible representation is a possible representation. Some of them
may be capable of a physical implementation.

Yes.

A POSSREP may or may not unambiguously define (either directly or
indirectly) a method for encoding values of type T on some physical
medium.

It is a possible representation of a POINT value which does correspond
to the mathematical term "Cartesian". However, CARTESIAN in the type
definition you quote is merely an arbitrary name for the POSSREP. It
just happens to have been chosen to remind us of the mathematical term.
Since your question refers to the name rather than the mathematical
term, it is meaningless.

Yes.

Yes. No. In that order. POINT is not defined in terms of physical
representations. It merely specifies that any implementation should
be capable of accepting or returning two values of type RATIONAL which
correspond to one of the two named POSSREPS. It is merely a convenience
for both user and implementer that the possreps are named after the
mathematical concepts that are intended to be used.

No and no. All that matters is that any implementation of the type uses
some valid physical representation and provides a suitable interface to
the declared possible representations.

Yes and yes.

CARTESIAN is not a physical representation, though a physical
representation of a POINT may use two instances of a physical
representation of a RATIONAL in such a way that they should be
interpreted as Cartesian co-ordinates in the mathematical sense.

And I assume that he does.

Yes.

Yes.

The footnote is referring to the accuracy of the use of terminology,
rather that the accuracy of physical representations of any type of
number in a computer.

Instead? - definitely not! But without that word you are correct.

Correct.

Correct.

The rational numbers are a subset of the real numbers. A floating-point
number is always an exact representation of some rational number,
which may be used as an approximation for an irrational number, or for a
rational number which can not be represented exactly in the floating-point
scheme being used. The numerator/denominator representation of a rational
number is not a 1-1 mapping of the possible values, nor is it convenient
for calculation, and it would not be used unless it was somehow the
whole point of the system being constructed.

THE_X returns a RATIONAL because it is the normal way to return a
component of one particular POSSREP. This is exactly and perfectly
appropriate. As an operator it is dependent on the specification of
the POSSREP. At the logical level, this has nothing to do with operators
on POINTS.

Yes, to an acceptable level of approximation if approximation will
be necessary.

Then yes (you cannot make a specification without some representation
to use in the rules of the specification) and then no. Of course a type
with no representation is not really very useful.

Yes. There is no problem with a representation that requires approximation
as long as this is stated, and as long as the expected accuracy is
also stated.

Of course not, why would anyone do that?

"The parameters to a given selector S constitute - necessarily -
a possible representation for <values of> the <type>." What some might
refer to as a "constructor", but which does not "construct" a value but
rather selects one of the members of the set of all possible values of
the type.

That the physical representation used within the implementation need not
be the same as any possible representation made available to the user,
and that the user is not entitled to make any assumptions about a type and
its values based on the physical representation that happens to be used.

A scalar is a single value of a single type. That there may be operators
which return other values of other types by operating on a scalar is not
relevant, those operators are simply part of the definition of the type.

A tuple is a finite set of scalars subject to certain conditions, and
a relation is a set of tuples subject to certain other conditions.

How can you have missed the entire point that it is essential to design
the logical model of your objects of interest without any consideration of
the strange tricks that the implementer had to use to produce a working
and reasonably efficient system to process your and other peoples
logical models?

If you make assumptions about your logical model based partly on knowledge
of a (not necessarily ideal or even optimal) platform implementation
you _will_ be confused, and you _will_ make mistakes.

Eric

On May 27, 6:55 am, Eric <e... (AT) deptj (DOT) eu> wrote:
Although what you are saying is conceivable, I would say from the
section titled "Possible Representations, Selectors, and THE_
Operators" on page 115 the reader is easily led to believe /possible
representation/ (which appears in bold typeface) means possible
physical representation. To paraphrase it states:

"Let T be a scalar type. ... physical representation of values of
type T is hidden from the user.... However, we do require that values
of type T have at least one *possible representation*..."

I can find no suggestion that a given possible representation doesn't
designate one of the physical representations mentioned in the
previous sentence of the same paragraph.


I think that creates confusion. It is crucial to know whether we're
dealing with a pure mathematical abstraction, or not. Are you saying
that POSSREPS are sometimes pure mathematical abstractions and
sometimes not?


Yes I was referring to the POSSREP named CARTESIAN. I was trying to
establish exactly what a POSSREP actually is. Are you saying the
question is meaningless because a POSSREP has nothing to do with the
physical representation?


I disagree with your latter comment. I'm sure we are meant to assume
that the X,Y components of the CARTESIAN POSSREP are associated with
the coordinate position of a given geometric point in a 2D Cartesian
plane, and the R,THETA components of the POLAR POSSREP are associated
with the modulus and argument of the geometric point. On that basis
there is a well defined conversion between those two representations.
There are also many operators that depend on this semantic, such as
the Euclidean distance between two points.

Since you are saying it is not strange, it seems you must be thinking
of a POSSREP as a pure mathematical abstraction. Is that right?

You don't appear to be completely consistent in the following sense:
Above you stated that a POSSREP may or may not unambiguously define a
method for encoding values of type T on some physical medium. For
those POSSREPs where it does I can only assume the POSSREP is not
abstract, because there is no way a pure abstraction could uniquely
specify a physical representation. I therefore conclude that it
doesn't make sense to define a type in terms of such a POSSREP.


That also seems to imply you think of a POSSREP as an abstraction,
completely independent of the physical.


Ok. If CARTESIAN is not a physical representation, then I would call
it a logical representation. But then I would never agree with Date
it is more accurate to use RATIONAL over REAL for the types of X,Y.


If it is indeed the case that Date thinks of POSSREPS as pure
abstractions, I find it remarkable that he doesn't say so explicitly,
and in fact easily gives the reader the opposite impression (see
above).

Also, I find his footnote about RATIONAL being more accurate than REAL
to strongly suggest he wasn't assuming a POSSREP is divorced from the
physical. On the contrary!


I don't accept that. I would say at a logical level of discourse the
reals are obviously most appropriate in computational geometry. One
would only consider using rationals because of implementation
concerns.


That word was in the context of applications using geometric points.
i.e. in the field of computational geometry where the reals are most
appropriate.


I disagree. I would say it is appropriate that at the logical level
of discourse THE_X is an operator that returns REAL. Otherwise it
imposes entirely unnecessary restrictions on physical implementation.


On the contrary, IMO it is better for a type system to allow for the
reals to be considered a type. I think there are advantages, and don't
see any difficulty when types are actually treated as pure
abstractions.

I think it is nonsense to define a type as a pure abstraction divorced
from the physical which must have a well defined set of legal values
and then leave it up to implementations to define only approximately
what those values actually are.


If you agree that the set of legal values of type POINT should be well
defined, then what would you say it should be? The only answer I can
think of that is independent of all reasonable physical
implementations is R^2. I believe any other answer imposes unnecessary
constraints on implementations. Q^2 is no good because I can easily
imagine an implementation using exact representations of countable
subsets of the reals that are sufficient for exact ruler and compass
geometry.


I would! The reals are clearly the most appropriate abstraction of
numbers in computational geometry applications.


I understand the difference between selecting a value and constructing
a variable. I don't see how you answered my question. Consider the
following literal:

radius(
boundingcircle(
triangle(
cartesian(0,0),
cartesian(1,0),
cartesian(0,1))))

I find it quite strange to say some of these operators are selectors
and some aren't. E.g. Date would say the operator that returns the
radius of a circle is not a selector, and names it THE_RADIUS. The
operator named boundingcircle returns the bounding circle of a given
triangle, which is uniquely defined for triangles with a nonzero
area. It is not clear to me whether Date would expect this operator
to be associated with another declared POSSREP of circle, in which
case the operator boundingcircle would be a selector. To me such
questions shouldn't arise in the first place at the logical level of
discourse. I regard this as a failure of properly separating the
logical and physical.



Fair enough, but I think Date overcomplicates things. My approach
would be simply to define a DDL that allows for types to be declared
that meet the crucial requirement that they are entirely abstract, and
then it is obvious that physical independence follows.


What do you mean by single value of a single type? It sounds like
another way of saying atomic which is meaningless to me. Can you
provide a mathematical definition? Why isn't a relation a single
value of a single most specific type?


I have not missed that simple point. Instead (and despite enormous
respect for Date) I find his approach to achieving that aim
complicated, confusing and even limiting.

I was for example asking for a definition of the term "hidden", but
not because I don't comprehend physical independence. Date claims
that the X component is visible in the POSSREP CARTESIAN but hidden in
the type POINT. I have no idea what that means, since the user can
for a given POINT value easily access a Cartesian representation at
the logical level of discourse using the relevant operators. That
comment would make slightly more sense to me if a POSSREP is a
possible /physical/ representation (because I can understand how the
physical is hidden from the user).

I believe there are much better approaches than Date's for providing a
clean logical-physical separation. I intend to post on that topic very
soon.

On May 27, 2:27 pm, David BL <davi... (AT) iinet (DOT) net.au> wrote:
Sorry, I somehow managed to look at "why would anyone do that?" and
saw "why would anyone define an uncountable type", and then forget how
I actually posed my question.

Ok, we agree there is no reason to outlaw uncountably infinite types.

BTW I'm sure I've read posts on this group that suggest uncountable
types are inappropriate in database theory. I think Jan Hidders has
made comments along those lines, defining "value of type" as something
capable of finite representation (I hope I'm not misrepresenting what
he's said).

David BL wrote:

You may be referring to the work Date, Darwen and Lorentzos did on
temporal databases and interval type generators. They made the pragmatic
decision to base their work on closed intervals over discrete, finite,
total orders.

Or you may be referring to instances where I observed how daft Joe is
for objecting to finite database operations on the basis of paradoxes
applying only to infinite sets.

Haven't gone through the other responses first, perhaps I should have,
but anyway here goes (see inlined answers) :

On 26 mei, 06:04, David BL <davi... (AT) iinet (DOT) net.au> wrote:
No. In fact when speaking very strictly, they never are. Physical
representations are sequences of bits, directed to the machine.
Logical representations are representations in terms of values (of
other types, except in the case of "basic" types such as
INTEGER, ...). Those values are intended for the human, and are, at
some point, always "tokenized" into text strings, because that's the
only way humans can ever perceive values spawned by the machine.

For example the temperature value zero degrees centigrade, might be
logically defined in terms of the number 273.16..., or it might be
logically defined in terms of the number 32, and showing such a value
to the user will require these numbers to be
"externalized"/"tokenized" into the text strings "273.16...",
"32", ...

Of course in many cases, one of the logical possreps will be the same
as the one on which the physical representation is based, e.g. the
physical representation for the temperature value "zero degrees
centigrade" might be based on the Fahrenheit temperature scale, and
thus the encoding of the number 32 will determine the bit pattern for
this temperature value, but strictly speaking, even then the
"physical" and the "logical" representations are still distinct.



Yes.


The POSSREPs as defined in the TTM literature have nothing to do with
physical encoding.



It could qualify as a valid POSSREP for the POINT type, but it is a
different one from the CARTESIAN possrep typically used in
Date&Darwen's relational writings.



Yes. In fact this holds for all of them, except then the "basic" ones
such as INTEGER, BOOLEAN, ...



See my previous remark. POSSREPs have nothing to do with physical
representations. So if he requires types to be defined in terms of
POSSREPs with components of other types, he is not relying on physical
representations.



D is targeted at defining/describing the abstractions, and nothing but
that. That approach does "separate out" the abstractions from the
physical, because the physical is left entirely unaddressed, and free
for the implementer to choose. In "Databases, Types and the
Relational Model", they further comment (something of the ilk) that
"of course there will have to be some kind of language that defines
the physical stuff, but we do not deal with that".



A type definition must have at least one POSSREP definition. A
POSSREP definition is a set of COMPONENTNAME/TYPENAME declarations,
plus an optional CONSTRAINT declaration. Hence a POSSREP definitions
depends on other types, and any constructs that are needed to build
valid CONSTRAINT expressions (essentially, these constructs are the
language's operators).

Of course, there is "intertwining" between type declarations and the
language's operators, because any type declaration automatically
brings a bunch of operators into existence, but strictly speaking, a
POSSREP definition does not depend on other POSSREP definitions, at
least not "directly". Of course it might depend on, e.g., the THE_
operators that are introduced into the language as a consequence of
the declaration of some other POSSREP, but that is not really a
"direct reference" to that other POSSREP.



Imo, there is great confusion over this subject, even in the TTM
discussion list. RATIONAL is often spoken of in a way that suggests
it is indeed a nominator/denominator pair, but your remark about SQRT
is valid. Date has a tendency to disregard "imprecise" stuff such as
the typical mantissa+exponent types, and the operators associated with
them.



My personal opinion : it's hard to tell what Date "thinks" on this
subject. I've never seen anything written that made that clear to me.



There may be prescriptions in the Manifesto that don't fully line up
with the properties of the typical mantissa+exponent types and the
operators associated with them. Perhaps (BIG perhaps !) that is the
reason for his tendency to disregard such types.



Don't see a problem. This operator coming into existence is a direct
consequence of the fact that POINT is declared to have an X component
of type RATIONAL in one of its declared possreps. So it's a direct
consequence of the type definition, which is itself also at the
logical level of discourse, no ?



From the manifesto :

"For all values v [of a type] and for all i [denoting the first,
second, third, ... component of some possrep], it shall be possible to
"retrieve" the value of Ci for v."

So, for all temperature values, it should be possible to retrieve
"THE_KELVIN" and "THE_FAHRENHEIT" and ...

However, it is nowhere stated that an invocation of such an operator
must also _succeed_ for all v !!! The manifesto is notoriously silent
on the subject of runtime exceptions.

Unless you interpret such a runtime exception as a "failure to
retrieve the Ci value", and thus as a violation of the prescription.
Under this interpretation, types must indeed be "complete" in the
sense you suggest.



His tendency to duck the issue of "imprecise" types and oprators, you
know ...



I wouldn't say he "outlaws" them. He merely observes that by
definition, such types cannot be handled by computer systems. He
merely observes that he cannot escape from that law, and therefore
bends with it. Just like we are forced to observe that we cannot
escape gravity (we can escape from the earth, but we cannot escape
from gravity).



You're right. The term was probably introduced to be able to speak of
"operators" in general, instead of having to continuously say
"operators and/or literals". Just like OO texts might want to talk of
"methods" in general, rather than "methods and/or constructors".

(Note that literals and selectors are not the same thing. All
literals are selectors, but not all value selectors are literals.
Literals are value selectors with no arguments, while there might be
other value selectors that do take arguments. But the term "value
selector" is restricted to those cases where the arguments match the
POSSREP declaration :

VAR RATIONAL X,Y;
VAR POINT P = CARTESIAN(X,Y); /* this is a value selector but not a
literal */
P = SHIFTHORZ(P, 2); /* allthough SHIFTHORZ returns a POINT value,
and must thus itself _contain_ a POINT value selector, SHITHORZ itself
is not a "value selector" */



It's not contradictory because all POSSREPs are logical, even if the
physical representation has a "remarkable resemblance" to one of them.



Date is on record saying that "the distinction [between scalar and
nonscalar] is probably not so important". And Darwen is on record
saying that "All types are first-class citizens.".

On 2011-05-27, David BL <davidbl (AT) iinet (DOT) net.au> wrote:
interconnected for point by point answers to be sensible now.

1. Even though the real/rational thing seems to have been your main point,
I want to ignore it for the moment. I believe that Date used "RATIONAL"
to be consistent with somewhere else, then felt it would be questioned,
so he added the footnote. So can we say that the declared POSSREPS
for POINT contain numbers of a suitable type and leave the choice of
type as a separate argument.

2. The logical model contains some types and operators sufficient for
what we actually want to do with our model.

3. The "suitable number type" is not part of this logical model,
because nothing is defined in terms of it, it is only used in some
possible representations.

4. A POINT is a scalar because it is not defined in terms of any other
type in the model.

5. The model is abstract because we could change the names of all the
types and it would still be a logically consistent system.

6. A POSSREP is equally abstract. All it does is specify a set of values
of certain types such that distinct sets of values correspond to
a unique value of the type having the POSSREP, and vice-versa. The
types used in the POSSREP need not be either defined or used in the
logical model.

7. There are two mappings of the logical model. The first is to objects
and actions in the real world. The names of types and operators in
the model are part of this mapping, as are the names and details of
any POSSREPS.

8. The second is to the top layer of the implementation of the system
which we use to "run" the model. Beyond this mapping is the only
place physical representations come into it.

In spite of what you say I suspect that you are sometimes crossing the
boundary between logical and physical. I also think you are causing
complications by wanting "abstract" to mean "completely mathematically
abstract".

Eric

On 2011-05-29, Erwin <e.smout (AT) myonline (DOT) be> wrote:

Eric

On May 29, 8:01 pm, Eric <e... (AT) deptj (DOT) eu> wrote:
I don't know what you mean by "nothing is defined in terms of it". I
would say the types, their possreps and various operators are all
defined in terms of the "suitable number type".


That doesn't make sense. POINT is defined in terms of two declared
POSSREPS that are in turn defined in terms of the declared types for
their components.


If the types used for components of the POSSREPs are undefined, then
the set of values of the type which is defined in terms of those
POSSREPs is undefined as well.


There are too many undefined terms in the above for me to comment.


I cannot comment on that unless you are more specific.

On May 29, 8:12 am, Erwin <e.sm... (AT) myonline (DOT) be> wrote:
What do you mean it could qualify as a valid POSSREP for POINT when
you just stated POSSREPS have nothing to do with physical encoding?


Would you say union types are defined in terms of POSSREPS?


I agree there is no problem assuming a POSSREP is at the logical level
of discourse. However, I would use REAL not RATIONAL.


I would define a literal to be any expression (of nested operator
invocations) containing no variables.

On page 117 Of Into, Date states:

"selector invocations - are a generalisation of the more familiar
concept of a literal (all literals are selector invocations, but not
all selector invocations are literals; in fact, a selector invocation
is a literal if and only if all its arguments are literals in turn)".