Re: Questions on possreps

On May 27, 6:55 am, Eric <e..._at_deptj.eu> wrote:
> On 2011-05-26, David BL <davi..._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.

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.

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

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?

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

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?

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

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.

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

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

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

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.

> And I assume that he does.

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!

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

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.

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

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.

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

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.

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

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.

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

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.

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

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

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

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.

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

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.

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

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?

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

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. Received on Fri May 27 2011 - 08:27:14 CEST