undefined | Better HN

0 pointsfspeech7y ago0 comments

I was wondering about termination. With finite ground facts that appears not to be an issue. Complexity is another matter.

0 comments

cfallin7y ago

Re: complexity, read up on "semi-naïve evaluation" for the usual execution strategy, which basically involves keeping lists of newly-added tuples in each iteration of the fixpoint loop and only processing deltas related to those new additions. This, combined with good index inference for each relation (predicate), so that e.g. the node-neighbor lookup is O(log |V|), should result in efficient execution...

JadeNB7y ago

Termination is achieved in brian_cloutier's example (https://news.ycombinator.com/item?id=19423320) by the use of different clauses (e.g., `Path` vs. `Edge`), so that all recursion is productive.

maweki7y ago

Datalog always terminates because there is no way to derive new atoms.

brian_cloutier7y ago

Yes, but there's more to it than just that. It's possible to write Prolog programs which never derive new atoms yet still fail to terminate.

It might be more accurate to say that Datalog programs cannot derive new atoms and this allows Datalog interpreters to use a search strategy which is guaranteed to terminate.

EDIT: Thinking about this more, I'm not sure why Prolog couldn't also use breadth-first search. So maybe both are necessary: Datalog not only disallows creating new atoms, but it also has a better search strategy; the combination of the two results in guaranteed termination.

1 more reply

YeGoblynQueenne7y ago

My understanding is that Datalog terminates because it does not allow functions as arguments to predicates. No functions means it's not possible to create infinite terms:

  P(f(x)).
  p(f(f(x)).
  p(f(f(f(x)))).
  ... etc

In fact I understand that termination is guaranteed even if a datalog program is executed by a Prolog interpreter. Or in other words, it's a result of the language semantics, not its implementation.

(but I might be wrong about this- corrections welcome).

1 more reply

j / k navigate · click thread line to collapse

0 comments

cfallin7y ago

JadeNB7y ago

Termination is achieved in brian_cloutier's example (https://news.ycombinator.com/item?id=19423320) by the use of different clauses (e.g., `Path` vs. `Edge`), so that all recursion is productive.

maweki7y ago

Datalog always terminates because there is no way to derive new atoms.

brian_cloutier7y ago

Yes, but there's more to it than just that. It's possible to write Prolog programs which never derive new atoms yet still fail to terminate.

It might be more accurate to say that Datalog programs cannot derive new atoms and this allows Datalog interpreters to use a search strategy which is guaranteed to terminate.

1 more reply

YeGoblynQueenne7y ago

My understanding is that Datalog terminates because it does not allow functions as arguments to predicates. No functions means it's not possible to create infinite terms:

  P(f(x)).
  p(f(f(x)).
  p(f(f(f(x)))).
  ... etc

In fact I understand that termination is guaranteed even if a datalog program is executed by a Prolog interpreter. Or in other words, it's a result of the language semantics, not its implementation.

(but I might be wrong about this- corrections welcome).

1 more reply

j / k navigate · click thread line to collapse