Re: [ontolog-forum] Complexity, efficiency, and the user language (was P

[Adrian Walker <adriandwalker@xxxxxxxxx>]

Hi John,

You wrote:

     a user-friendly system could use *one* very expressive
     language, compile it to a common intermediate form (e.g. Datalog)
     and optimize it for any data organization.  It could also automate
     the caching and/or indexing of frequently used data.

+1, since there's a running system out there on the web that does pretty much just that.  Not for *any* data organization, but it automatically generates and runs networked SQL that would be too complicated to write reliably by hand.  It's online at the site below, and shared use is free.

Apologies to folks who have seen this before.

                                                    -- Adrian
                
Internet Business Logic
Open Apps for Open Data
A Wiki and SOA Endpoint for Apps written in Executable Open Vocabulary English over SQL and RDF
Online at www.reengineeringllc.com  
Shared use is free, and there are no advertisements

Adrian Walker
Reengineering

On Tue, Oct 29, 2013 at 1:32 PM, John F Sowa <sowa@xxxxxxxxxxx> wrote:

Michael and Benjamin,

I changed the subject line to emphasize the issues.

MB
> But let's not forget that what decides tractability and
> feasibility of a certain technology is the problem at hand.
> Recently, I wrote a SPARQL UPDATE query to emulate a PDP-1
> just for fun. It is 50 million times slower than a C++ emulator
> (see http://www.brunni.de/pdp1/ ).

That is similar to an exercise I used to compare Prolog and SQL.
Both of them are logic-based systems that use closely related
algorithms under the covers.

So I rewrote some typical Prolog exercises in SQL.  For those
problems, SQL was much, much slower, but not quite as bad as
50 million times.  Some observations:

  1. The Datalog subset of Prolog can be used to express SQL and
     SPARQL queries.

  2. But the software for each of those three systems is optimized
     for different kinds of environments:

     a) Prolog was designed to run in RAM (or at least virtual RAM).
        It is designed for programmers who understand the basic
        implementation:  backtracking, indexing methods, and some
        "impure" methods (procedural hacks) to improve performance.

     b) SQL was designed for a database organized as tables stored on
        local disks.  SQL systems optimize queries by compiling them
        to a more efficient form (with methods similar to those that
        Prolog programmers routinely use to optimize their code).

     c) SPARQL was designed for accessing data located in documents
        on the Internet.  The access times can be much worse than a
        local disk, not to mention RAM. The indexing and optimization
        of SQL and Prolog is, in general, not possible.

  3. However, the same queries (stated in Datalog or any syntactic
     sugar) could be translated to and executed by the above systems.

  4. Therefore, a user-friendly system could use *one* very expressive
     language, compile it to a common intermediate form (e.g. Datalog)
     and optimize it for any data organization.  It could also automate
     the caching and/or indexing of frequently used data.

  5. For the example of the PDP-1 emulator, a good Datalog implementation
     would start by running as slow as SPARQL.  But as it accumulated
     the reusable data in its cache (virtual RAM on a system with 64-bit
     addresses), it would speed up.  With good compilers its speed could
     be comparable to the C++ version.

MB
> complexity and decidability are central issues as more expressiveness
> makes accidental intractability more probable.

A well-designed optimizer would *never* cause accidental intractability.
Compilers and optimizers have been implemented and used in database
and knowledge base systems for over 30 years.  See

    http://www.jfsowa.com/pubs/fflogic.pdf
    Fads and fallacies about logic

BG
> I recommend you look at the AAAI-13 long rules tutorial, esp. its
> first section, which discusses how (semantic) rules are useful
> in more specific or indirect ways, in addition to the general
> and direct characteristics of understandability and reusability.

Two points:

  1. I basically agree.  But it's important to emphasize the need
     for and the ability to implement appropriate compilers and
     optimizers to avoid the "accidental intractability".

  2. Any references to recommended reading should include a URL.

Fundamental principle:  Reducing the expressive power of the
logic can *never* improve efficiency.  Its primary effect is
to make some problems impossible to state.  In fact, it can
even make the language more difficult to learn and use.

John

_________________________________________________________________
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

_________________________________________________________________
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    (01)