ontolog-forum
[Top] [All Lists]

## Re: [ontolog-forum] blogic iswc keynote

 To: "[ontolog-forum]" "Rob Akscyn" Thu, 17 Dec 2009 10:29:52 +1300 (NZDT) <52262.74.98.253.220.1260998992.squirrel@xxxxxxxxxxxxxxxxxxxxxxxxxx>
 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)
 Current Thread [ontolog-forum] blogic iswc keynote, Rick Murphy Re: [ontolog-forum] blogic iswc keynote, Peter Yim Re: [ontolog-forum] blogic iswc keynote, John F. Sowa Re: [ontolog-forum] blogic iswc keynote, Christopher Menzel Re: [ontolog-forum] blogic iswc keynote, Rick Murphy Re: [ontolog-forum] blogic iswc keynote, ravi sharma Re: [ontolog-forum] blogic iswc keynote, Ali Hashemi Re: [ontolog-forum] blogic iswc keynote, sowa Re: [ontolog-forum] blogic iswc keynote, sowa Re: [ontolog-forum] blogic iswc keynote, Rob Akscyn <= Re: [ontolog-forum] blogic iswc keynote, Christopher Menzel Re: [ontolog-forum] blogic iswc keynote, John F. Sowa Re: [ontolog-forum] blogic iswc keynote, Christopher Menzel Re: [ontolog-forum] blogic iswc keynote, John F. Sowa Re: [ontolog-forum] blogic iswc keynote, Christopher Menzel Re: [ontolog-forum] blogic iswc keynote, John F. Sowa Re: [ontolog-forum] blogic iswc keynote, Rich Cooper Re: [ontolog-forum] blogic iswc keynote, sowa Re: [ontolog-forum] blogic iswc keynote, Rich Cooper Re: [ontolog-forum] blogic iswc keynote, Chris Partridge