[Top] [All Lists]

Re: [ontolog-forum] blogic iswc keynote

To: ontolog-forum@xxxxxxxxxxxxxxxx
From: sowa@xxxxxxxxxxx
Date: Wed, 16 Dec 2009 18:01:27 -0500 (EST)
Message-id: <758494eed214ed87a635a1d672b83b62.squirrel@xxxxxxxxxxxxxxxxxxxx>

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

would be possible.  However a direct pointer to a disk location
make updates and conversions more time consuming.  If we
assume that
there is a fair amount of turnover in the DB, the files would
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),
pointer to every record would have to be found and changed.
would include not just the records in the EMPLOYEES table,
but every
table in the DB that might refer to entries in the
table.    (09)

In any case, I was just pointing out that databases tend
to be
highly optimized for processing queries stated in FOL.  If
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)

<Prev in Thread] Current Thread [Next in Thread>