John, (01)
Thanks for another insightful note. (02)
There was one part I did not understand and thus would benefit from your
knowledge: (03)
You said: (04)
>
> 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. (05)
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). (06)
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). (07)
Granted, for pragmatic reasons, databases in general aren't 'compiled' to the
point of
eliminating all such levels of indirection (I presume) [i.e., we generally have
to
search for the manager's salary using his name, and thus having to do that in
log time].
But how is the number of dollars for an employee's salary (in effect a pointer
to an
integer: how many cents he/she makes in a year) any different from a
pointer/number/proxy-name for a manager? (08)
If I need to know the names of the managers I can make that be another step
(i.e., now
up to 3N steps total) but those names are not needed to answer the query as
posed. (09)
***** (010)
So, Obewan, I await your sage advice! :-) (011)
Cheers,
Rob
********* (012)
>
> Even complex queries can be evaluated efficiently if they
> process
> a subset of the database. Suppose that the complex condition
> in the
> following query takes time proportional to the cube of the
> number of
> entries:
>
> For all employees in department C99,
> find [complex condition].
>
> If a company has 10,000 employees, N3
> would be a trillion. But if there
> are only 20 employees in department
> C99, then 203 is only 8,000.
>
> In summary, computational
> complexity is important. But complexity is
> a property of algorithms,
> and only indirectly a property of problems,
> since most problems can
> be solved by different algorithms with different
> complexity. But The
> language in which a problem is stated has no effect
> on complexity.
> Reducing the expressive power of a logic does not solve
> any problem
> faster; its only effect is to make some problems impossible
> to
> state.
>
>
>
>
>
> _________________________________________________________________
> 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
>
> (013)
_________________________________________________________________
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 (014)
|