[Top] [All Lists]

Re: [ontolog-forum] blogic iswc keynote

To: ontolog-forum@xxxxxxxxxxxxxxxx
From: sowa@xxxxxxxxxxx
Date: Wed, 16 Dec 2009 15:27:29 -0500 (EST)
Message-id: <44454260261c852da515e7c1420b29e8.squirrel@xxxxxxxxxxxxxxxxxxxx>

Rick,    (01)

RM> Would you have a recommendation for generating
> that's a bit more agile than crocheting ?    (02)

Please remember that CLIF and CGIF have been designed as
*interchange formats* for an open-ended number of different,
compatible kinds of logics.  Every implementation of any
one of those
subsets *is* an implementation of Common Logic.    (03)

I noticed that
in the Q/A section of Pat's talk, somebody said
that CL is too
expressive -- therefore, it is inefficient.    (04)

But that question
is hopelessly confused.  It is based on the
assumption that there is
*one and only one* method of using or
reasoning with any given
logic.   But that assumption does not
hold for *any* natural
language, programming language, query
language, or, indeed, any
version of logic.    (05)

For example, the WHERE clause of SQL has the
full expressive
power of FOL.  That makes FOL the most widely used
version of
logic on planet earth.  But nobody uses SQL for theorem
See the discussion below.    (06)

As another example, Cyc
has a very expressive language, but they
use 27 different inference
engines to reason about it.  For each
problem, the system
automatically selects the appropriate engine.    (07)

_________________________________________________________________    (08)

Execerpt from http://www.jfsowa.com/pubs/fflogic.pdf    (09)

For database queries and constraints, SQL supports full FOL, but
even the worst case examples can be evaluated in polynomial time,
and the most common queries are evaluated in linear or logarithmic
time.  That performance enables SQL algorithms to process terabytes
or petabytes of data and makes first order logic, as expressed in
SQL, the most widely used version of logic in the world.    (010)

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:    (011)

   Find John Doe’s department, manager, and
salary.    (012)

If there are N employees, the time for the following
query is
proportional to (N log N):    (013)

   Find all employees
who earn more than their managers.    (014)

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.    (015)

Even complex queries can be evaluated efficiently if they
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:    (016)

   For all employees in department C99,
find [complex condition].    (017)

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.    (018)

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
state.    (019)

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

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