Rob, (01)
RA> There was one part I did not understand and thus
would benefit
> from your knowledge: (02)
JFS> As an
example, the SQL translation of the following query would be
>
answered in logarithmic time if the employee relation is indexed on
> the name field:
>
> Find John Doe’s department,
manager, and salary.
>
> If there are N employees, the
time for the following query is
> proportional to (N log N):
>
> Find all employees who earn more than their
managers.
>
> This query would take N steps to find the
manager and salary
> of each employee. The (log N) factor is
needed to find the salary
> of each employee's manager. (03)
RA> I did not understand why log N time is needed to find the
salary
> of the manager (if you'd said "(log M) time"
where M is the number
> of managers I would have been half-way
there). (04)
The time can vary, depending on how the DB is
organized. I assumed
the following organization for a table called
EMPLOYEES: (05)
1. A large table, indexed by the employee name,
which would contain
various information for each employee: name,
address, manager,
salary, etc. (06)
2. Each entry in the
table would be a character string rather than
a more direct
pointer to a specific record on a disk. (07)
RA> But if lookup of
a N employees' salaries is N steps, and if the
> entry for their
manager were a pointer (i.e., a locator not a name)
> then I would
think getting the manager's salary to do the salary-
> comparison
would be 'just another step' (i.e., a total of 2N steps). (08)
That
would be possible. However a direct pointer to a disk location
would
make updates and conversions more time consuming. If we
assume that
there is a fair amount of turnover in the DB, the files would
have
quite a few holes with unused space for employees who left.
If we
tried to reclaim the space (or if we migrated to new hardware),
every
pointer to every record would have to be found and changed.
That
would include not just the records in the EMPLOYEES table,
but every
table in the DB that might refer to entries in the
EMPLOYEES
table. (09)
In any case, I was just pointing out that databases tend
to be
highly optimized for processing queries stated in FOL. If
you
want to optimize them further, that just confirms my point. (010)
John (011)
_________________________________________________________________
Message Archives: http://ontolog.cim3.net/forum/ontolog-forum/
Config Subscr: http://ontolog.cim3.net/mailman/listinfo/ontolog-forum/
Unsubscribe: mailto:ontolog-forum-leave@xxxxxxxxxxxxxxxx
Shared Files: http://ontolog.cim3.net/file/
Community Wiki: http://ontolog.cim3.net/wiki/
To join: http://ontolog.cim3.net/cgi-bin/wiki.pl?WikiHomePage#nid1J
To Post: mailto:ontolog-forum@xxxxxxxxxxxxxxxx (012)
|