Incremental Tabling

It would be amusing to do the same page in SQL (and PL/SQL) or LINQ or some other database-oriented tool.

If a more compact syntax is desired, there’s Yedalog, which is essentially datalog that abstracts over databases, streams, files, map-reduce, etc. (I’m not aware of any open source implementation.)

There is this Oracle product named “APEX”. Since SQL + PL/SQL is so horrible for making websites, Oracle made this thingy that lives in the database but renders web pages. They used it to make a web-based GUI for making web-based GUIs. So basically your tables and forms and such are just SQL queries, the UI for making the UI reminds me a little bit of Borland Delphi.

I think I completely misunderstood your comment :wink:

Here is what it looks in SQLite:

$ sqlite3 
SQLite version 3.29.0 2019-07-10 17:32:03
Enter ".help" for usage hints.
Connected to a transient in-memory database.
Use ".open FILENAME" to reopen on a persistent database.
sqlite> create table person_age ( name text, age number );
sqlite> insert into person_age values ( 'Rud', 6 );
sqlite> select age from person_age where name = 'Rud';
6
sqlite> insert into person_age values ( 'Uth', 11 );
sqlite> select age from person_age where name = 'Uth';
11
sqlite> insert into person_age values ( 'Shicumar', 119 );
sqlite> insert into person_age values ( 'Sho', 91 );
sqlite> insert into person_age values ( 'Ari', 5 );
sqlite> create view younger_older as
   ...> select younger.name younger_name, older.name older_name
   ...> from person_age younger, person_age older
   ...> where younger.age < older.age;
sqlite> select * from younger_older where younger_name = 'Rud' and older_name = 'Uth';
Rud|Uth
sqlite> select younger_name from younger_older where older_name = 'Uth';
Rud
Ari

So basically the same, but again, this is a very basic example. The one obvious (mis-) feature of Prolog is that it is quite easy to make non-terminating queries. A recursive query in SQLite (or CONNECT BY in Oracle) does whan you mean it to do without tricks.

We now have incremental tabling for that :slight_smile: Surely the Prolog version is much more compact :slight_smile:

4 Likes

Writting SQL was never fun and it will never be. And, I still have to meet the person who does not have to look at railroad diagrams to write it. I don’t think it is the verbosity alone, there is something deeply wrong with SQL.

I just wanted to show Peter how exactly it would look :wink:

1 Like

Hello Jan,

on a more serious note, it is very important for me to know the limits and the gotchas of any technology I have to use. I know that it sometimes sounds like nitpicking or just being negative, but this is kinda unavoidable.

(In experimental science, hiding negative information is used as a weapon in the inter-lab wars; if your competitor does not know what you tried and failed, they are most probably gonna waste time and money trying it and failing it themselves.)

What do you want to say? Tabling with well founded semantics and incremental tabling are well described in the (XSB) literature. We are currently migrating this technology to SWI. There will be a proper description in the manual and additional reports and publications. And there is the source :slight_smile:

So, nothing is hidden. The learning curve might be steep though. From a declarative point of view, tabling with well founded semantics is fairly easy. From a procedural point of view it is pretty hard to grasp.

1 Like

Hi, I wanted to say something completely different, but I said it very badly. I meant nothing about tabling in particular. It was also not related to the original post, so let’s just forget about it.

Thanks for reminding me about SQL “create view”. I’ve written DB2, Oracle, MySQL, SQLite, and each of them was painful, so I suppose my brain has just hidden away as much as possible of the pain. :wink:

SQL:Prolog :: COBOL : Python

These are helpful but not enough. I once tried to write some graph-traversal code using XSB tabling … it was great for queries like “is there a path” and “find shortest path” but not for “find path with the traversed nodes” (I forget the details, but David Warren also got stuck on it - the problem was that the tabling implementation didn’t have the ability to specify that some of the parameters didn’t need to be used). As soon as we’re out of Datalog territory and arbitrary terms can show in the query, it’s not obvious what is easy to do and what isn’t with tabling.

Part of “deeply wrong” is the way SQL mixes row results with set/bag results. In Prolog, I can use bagof (or setof) and member to go back and forth between these but SQL mixes them in weird ways (and also gets “DISTINCT” wrong).

There are also many of other things that are wrong in SQL, such as the poor semantics for NULL. For example sum(a+b) != sum(a)+sum(b):

sqlite> create table T(A,B);
sqlite> insert into T values (0,1);
sqlite> insert into T values (1,null);
sqlite> select sum(A)+sum(B) from T;
2
sqlite> select sum(A+B) from T;
1

Could this be long ago before answer subsumption (aka mode directed tabling) was added? Of course you cannot answer “Give me all paths from A to B” if the graph is cyclic as there are infinitely many. Using answer subsumption though, you can find the actual shortest path and even all acyclic paths.

The trick is that you do not table some arguments but instead run some aggregation function on the answers produced in the non-tabled arguments. These days, AFAIK, all Prolog systems that implement tabling provide answer subsumption.

1 Like

I would love to see a demo program of graph traversal using answer subsumption.

Its in the docs: https://www.swi-prolog.org/pldoc/man?section=tabling-mode-directed

3 Likes

OK, that’s awesome!

Is there a doc somewhere that explains why tabling is superior for graph traversal over just writing Prolog code directly to do that? Tabling is one of those SWI-Prolog features that I just don’t understand the use case for yet.

I’m pretty sure that was available (XSB version 3.7?). (But this was 5+ years ago; memories fade and I don’t have access to the code or emails I wrote then … I suppose I could ask David Warren if he remembers …)

I would love to see a program that finds all acyclic paths and not just the shortest. The problem I encountered was that one of my arguments was building the list of visited nodes, and there didn’t seem to be any way to “subsume” these, which would have allowed terminating the computation. The only alternative would seem to be recording the visited nodes, e.g. with b_setval/2, which I don’t think XSB had. But using globals is something I’d prefer to avoid.

(It’s also possible XSB version 3.8 has added some features that would solve the problem.)

You can think of tabling as a more general version of memoization. In the case of graph traversal, tabling allows detecting a cycle because the Prolog engine can say “I’ve been here before, so if what I’ve seen already has a solution, I can just re-use it.” Without this, you have to write your own cycle detection and your own aggregation; tabling will detect cycles and will do the aggregation for you (you need to provide the aggregation predicate, such as shortest/3 in the example). (See also dynamic programming.) There’s quite a bit more to tabling than this, which is why the XSB group has spent such a long time working on it — and I hope they eventually get lots of credit for this important work.

1 Like

It would be well deserved. XSB brings a lot of the goodies of Datalog and Answer Set Programming together with the old Prolog goodies in one system. All this didn’t get much of my attention. I think that was a mistake. I’m glad this stuff comes to SWI. Next, a lot of work needs to be done to convince the world that this is a good idea.

3 Likes

An explanation:

1 Like

Nice.

Had a similar session … and instead of older, it was about cousins.

There is something really nice when you can describe and don’t have to look under the hood of things to make them work – tabling will be a great part of it.

Dan