Re: Questions on possreps
Date: Thu, 26 May 2011 23:55:17 +0100
Message-ID: <slrnittmil.cjt.eric_at_teckel.deptj.eu>
On 2011-05-26, David BL <davidbl_at_iinet.net.au> wrote:
> 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)?
No. A possible representation is a possible representation. Some of them may be capable of a physical implementation.
> 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?
Yes.
> 3) Is it correct that a POSSREP typically doesn't unambiguously define
> a method for encoding values of type T on some physical medium?
A POSSREP may or may not unambiguously define (either directly or indirectly) 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?
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.
> 5) Is it correct to say that in Tutorial D types are sometimes defined
> in terms of possreps?
Yes.
> 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)?
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.
> 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?
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.
> 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; };
Yes and yes.
> 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?
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.
> 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?
Yes.
> 10) Is Date probably thinking that a floating point representation is
> in practise used for RATIONAL?
Yes.
> 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?
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.
> 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:
Instead? - definitely not! But without that word you are correct.
> a) since only certain rationals can be represented exactly, we are
> forced to represent most numbers only approximately.
Correct.
> b) given that the operations are typically approximate, the results
> of calculation are typically approximate. Therefore the floats
> themselves are an approximation.
Correct.
> 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.
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.
> 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;
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.
> 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"?
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.
> 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?
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.
> 16) Does Date outlaw types which are uncountably infinite (because
> there is no representation with a finite encoding for every value)?
Of course not, why would anyone do that?
> 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?
"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.
> 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?
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.
> 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?
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.
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 Received on Fri May 27 2011 - 00:55:17 CEST