![](/i/fill.gif) |
![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
From: Nicolas Alvarez
Subject: Re: Binary trees, branches and leaves
Date: 4 Mar 2010 21:58:24
Message: <4b907350@news.povray.org>
|
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
Darren New wrote:
> Ideally, for example, you'd have no "unique
> IDs" in your database - the only reason you do is that some real-world
> items have unique properties that you can't digitize.
Hmm...
Suppose I have "tasks" (CPU-intensive processing tasks, such as rendering a
certain frame of a certain POV-Ray scene at specified settings). I store
those tasks in a relational table. Each task has a unique *name*.
I have another table that holds information about input files, such as the
.pov. And a third table that links the task and file tables together, since
it's n-to-n (a task may use multiple files, a file may be used by multiple
tasks).
From a *practical* point of view... Should that link table refer to tasks by
their names? It's a known unique property, and I can "digitize" it. Or
should I add a numerical "unique ID" to the task table, and use that from
the link table, with the purpose of needing less storage for the link table
and making lookups faster? Heck, would integers *be* faster than strings,
if I use indexes in either case?
Post a reply to this message
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
Nicolas Alvarez wrote:
> From a *practical* point of view... Should that link table refer to tasks by
> their names?
It should refer to the task table by its primary key. Assuming users adding
tasks are required to pick unique (and hopefully meaningful) names, that
would be a good primary key. If there's nothing else actually unique about
the job, then a uniqueID field is about as well as you can do. But you can
almost always find something unique, like timestamp+submitter.
Now, if you're going to start mucking up your relational model because it's
too slow, first ask yourself if it's actually too slow. :-) Alternately, add
a *second* unique key, and put that in both tables, just for efficiency.
> It's a known unique property, and I can "digitize" it.
By "digitize", I meant stuff like each customer is actually unique, but what
makes that customer unique is not something that's easy to get into the
database. Every attribute of an actual customer that's easy to put into a
database is also something that a customer might change some day. Phone
number? Obviously not. Name? Hope they don't get married. Etc. Tax number?
Hope they don't change citizenship. Etc.
--
Darren New, San Diego CA, USA (PST)
The question in today's corporate environment is not
so much "what color is your parachute?" as it is
"what color is your nose?"
Post a reply to this message
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
Darren New wrote:
> The point of relational is to make
> the data unrelated to the actual code that uses it, but rather related
> to the real world stuff it represents.
One of the points of a relational database is that several programs can
use the data, possibly in ways not originally envisaged. If you make the
data related to the code that uses it... it's kind of hard to use it in
new, unexpected ways.
Today, lots and lots of people seem to forget this. They think of a
database as being a system for holding data that only one application
uses and only that application understands. This isn't what a database
is supposed to be. It's supposed to facilitate access by multiple programs.
> Ideally, for example, you'd have
> no "unique IDs" in your database - the only reason you do is that some
> real-world items have unique properties that you can't digitize.
Or sometimes it's just for performance. An order can be completely
identified by the customer it's for, the date it was placed, and what
was ordered. But that's a heck of a lot of information for a key. (In
fact, that *is* the entire order!) Having an artificial key [to use the
technical term] is much more convinient - especially if you want to
refer to the order from outside the database (e.g., over the phone).
Post a reply to this message
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
One interesting question: If objects are in an array rather than being
individually allocated (and handled through references/pointers), can it
still be called object-oriented? (I'm not talking about an array of
references to objects, but an array of actual objects.)
For example a heap (ie. what is used eg. in heap sorting) is an extremely
ingenuous form of binary tree in that all the elements in a heap can be
stored in an array and they require no ancillary data whatsoever (ie.
left/right/parent pointers or anything). Elements can be added and removed
from the heap in O(log n) regardless of this. (About the only thing that
is guaranteed about the distribution of the elements in the heap is,
however, that the largest element will always be at the root. However,
even this guarantee is quite useful in many tasks, such as maintaining
a fast priority queue or heap sorting.)
The advantage of a heap is, of course, that it consumes the least amount
of memory because all the objects are in a contiguous array, rather than
being allocated individually and handled through references/pointers.
However, can this be called object-oriented? Having objects in an array
excludes the possibility of using objects of a derived type (unless an
object of the derived type has the exact same size as the base type object;
even then it requires some low-levelish trickery to get it working, at
least in C++, and probably other languages where objects can be handled
by value and put into arrays). However, one of the basic ideas of OOP is
that whenever an object of type A is expected, an object of type B can be
given to it instead, if B has been derived from A (or from any of its
subclasses). An array of objects wouldn't support this.
--
- Warp
Post a reply to this message
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
Warp wrote:
> However, can this be called object-oriented? Having objects in an array
> excludes the possibility of using objects of a derived type (unless an
> object of the derived type has the exact same size as the base type object;
> even then it requires some low-levelish trickery to get it working, at
> least in C++, and probably other languages where objects can be handled
> by value and put into arrays). However, one of the basic ideas of OOP is
> that whenever an object of type A is expected, an object of type B can be
> given to it instead, if B has been derived from A (or from any of its
> subclasses). An array of objects wouldn't support this.
Wouldn't you just need to determine the storage requirements of THE
LARGEST class of object? And allocate that amount for every object?
Granted, I don't actually know of a language or compiler which actually
supports this...
(In particular, if you can add new subclasses dynamically at runtime,
this approach obviously won't work at all. But if all classes are known
at compile-time, it's feasible in principle.)
Post a reply to this message
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
Invisible <voi### [at] dev null> wrote:
> Wouldn't you just need to determine the storage requirements of THE
> LARGEST class of object? And allocate that amount for every object?
No, because indexing is done based on the type of the array. For the
indexing to work properly the array type would have to be that of the
largest object type, but then you wouldn't be able to easily store any
other type of objects there (because now you would be handling objects
of the most derived class type rather than objects of the base class
type).
You could probably get around this limitation by creating an array
container class which handles the memory allocation and indexing using
low-level functionalities (raw pointer arithmetic and such), but it would
be quite a hack. And you wouldn't be able to use pointer arithmetic on
the array directly (except by using more abstract iterators).
Then there's the problem of assigning objects: If you assign an object
to a place in the array where there's already an object, and they are of
different types... I don't think it would work. Maybe you could get around
it by first destroying the existing object and then placing the new object
in its place using placement new, but it becomes complicated.
Perhaps not *impossible*, but as you may guess, quite hard and kludgey.
--
- Warp
Post a reply to this message
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
>> Wouldn't you just need to determine the storage requirements of THE
>> LARGEST class of object? And allocate that amount for every object?
>
> No, because indexing is done based on the type of the array. For the
> indexing to work properly the array type would have to be that of the
> largest object type, but then you wouldn't be able to easily store any
> other type of objects there (because now you would be handling objects
> of the most derived class type rather than objects of the base class
> type).
You seem to be looking at "can you do this in an existing language?" I'm
looking at "is it feasible for a hypothetical OO language to support
this efficiently?" I think it could be supported efficiently; I just
can't think of any language which does it.
> Perhaps not *impossible*, but as you may guess, quite hard and kludgey.
Not if it's hard-wired into the language. Then it becomes no less hard
or kludgey than (say) generating the illusion that each program on the
machine has complete control of the entire machine, when in reality the
OS is time-slicing them and sharing memory and I/O resources between them...
Post a reply to this message
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
Invisible wrote:
> One of the points of a relational database is that several programs can
> use the data, possibly in ways not originally envisaged.
I'd go so far as to say that was the *primary* point. We already had
standard database stuff using pointers, called CODASYL. It sucked if you
wanted to do anything unexpected with it.
> Today, lots and lots of people seem to forget this. They think of a
> database as being a system for holding data that only one application
> uses and only that application understands. This isn't what a database
> is supposed to be. It's supposed to facilitate access by multiple programs.
This si why I laugh at people who say it's better to put the data
consistency assurances in the program.
> Or sometimes it's just for performance. An order can be completely
> identified by the customer it's for, the date it was placed, and what
> was ordered.
Well, probably customer and timestamp. You don't have to know what they
ordered at 14:01 on Jan 23 to find it. The artificial key, being artificial,
is a secondary key, not a primary key. Unless it is printed on the physical
slip you used to take the order, like at a restaurant or something.
--
Darren New, San Diego CA, USA (PST)
The question in today's corporate environment is not
so much "what color is your parachute?" as it is
"what color is your nose?"
Post a reply to this message
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
Warp wrote:
> One interesting question: If objects are in an array rather than being
> individually allocated (and handled through references/pointers), can it
> still be called object-oriented?
I would think so. Inheritance is just one part of the OO thing.
> An array of objects wouldn't support this.
It could, if you allocate enough space in the array for child types. Of
course this breaks if you start loading new child classes at runtime. You
just artificially inflate the size you allocate to be large enough.
You're also running into the covariance problem. If you have
virtual A* x(B*) { ... }
(i.e., a function x that take an instance of B or one of B's subclases as an
argument, and returns an instance of class A or one of A's children...)
what is a subclass that overrides that x allowed to declare as a return type
and an argument type? Is it allowed to accept only C*, where C is a child
of B? Is it allowed to accept D*, where D is a parent of B? Now ask the
same about A, and you get a completely different answer.
--
Darren New, San Diego CA, USA (PST)
The question in today's corporate environment is not
so much "what color is your parachute?" as it is
"what color is your nose?"
Post a reply to this message
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
Invisible wrote:
> I think it could be supported efficiently; I just
> can't think of any language which does it.
C# lets you declare arrays of objects that are inline like C++, and the
generic "List" class will generate special versions when you instantiate it
with a class that is pass-by-value, but the nature of the pass-by-value
objects is that you can't inherit from them and add any fields, so the
question doesn't come up.
>> Perhaps not *impossible*, but as you may guess, quite hard and kludgey.
>
> Not if it's hard-wired into the language.
Yeah. C++ style OO is kludgey in C. That's why cfront was written. :-)
--
Darren New, San Diego CA, USA (PST)
The question in today's corporate environment is not
so much "what color is your parachute?" as it is
"what color is your nose?"
Post a reply to this message
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |