Michael and Benjamin, (01)
I changed the subject line to emphasize the issues. (02)
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/ ). (03)
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. (04)
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: (05)
1. The Datalog subset of Prolog can be used to express SQL and
SPARQL queries. (06)
2. But the software for each of those three systems is optimized
for different kinds of environments: (07)
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. (08)
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). (09)
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. (010)
3. However, the same queries (stated in Datalog or any syntactic
sugar) could be translated to and executed by the above systems. (011)
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. (012)
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. (013)
MB
> complexity and decidability are central issues as more expressiveness
> makes accidental intractability more probable. (014)
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 (015)
http://www.jfsowa.com/pubs/fflogic.pdf
Fads and fallacies about logic (016)
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. (017)
Two points: (018)
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". (019)
2. Any references to recommended reading should include a URL. (020)
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. (021)
John (022)
_________________________________________________________________
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 (023)
|