What is the difference between naive and semi naive evaluation?

Question

I have been trying to implement an algorithm for the semi naive evaluation of a datalog program but couldn't get a straight answer anywhere that explains the difference in simple words.

According to my understanding naive is a bottom-up evaluation technique so it is semi-naive.

In the first iteration, both evaluation techniques start with an empty set.

As the iterations proceed further both end up having iterations and producing tuples until a new tuple is reached.

So the semi-naive starts from the head or body of the rule?

path (X,Y):- edge(X,Y).

path (X,Y):- edge(X,Z),path (Z,Y).

Can someone please explain how the EDB and IDB get updated at the end of each iteration for the above program. Are the tuples stored under each predicate? Like a separate column for edge and a separate column for the path or they get stored as a collection.

Also, what is the difference between global and local unification?

Answer 1

This algorithm has been named the naive algorithm for datalog evaluation. The basic idea of the semi naive algorithm is to concentrate, to the extent possible, on the new facts generated at each level and thereby avoid recomputing the same facts." — Foundations of Databases (TOC).

The difference between the naîve and semi-naîve evaluation in Datalog is that when you're evaluating using the naïve implementation you take all the initial dataset (existing EDBs) plus the news ones (inferred EDBs) for each iteration. For example, if you have the IDBs like this:

reachable(X,Y) :- link(X,Y).

reachable(X,Y) :- link(X,Z), reachable(Z,Y).

And a set of EDBs like this: link = {(a,b), (b,c), (c,c), (c,d)} The procedure for execute the evaluation is: 

1. Begin by assuming all IDB relations are empty. 

2. Repeatedly evaluate the rules using the EDB and the previous IDB to get a new IDB. 

3. End when there is no change to IDB.