I totally thought the article was going to be about prolog. Datalog was formulated as a subset of prolog. Prolog generalizes datalog, and is functional, etc. So generalizing a language that was the subset of a larger one in the first place is something I find odd.
Prolog is not functional. Datalog literals [1] and arguments of literals cannot have as arguments functions of arity more than 1 (i.e. constants). Prolog literals and their arguments may have functions of arity more than 1 as arguments.
However, Prolog predicates are relations, not functions. i.e. they have no fixed "input" and "output" arguments. So Prolog is not a functional language.
Has anyone had experience with Datalog or Datafun? What was the programming experience like? What did you build with it? Did you find that you were more productive or less? What sorts of problems was it a good fit for, and what sorts of things was it a bad fit for?
For my database course I had to write all queries in: SQL, Relational Algebra, and Datalog. I remember that Datalog was the easiest way of writing queries if you understood all the tricks. However, this was on paper, never executed on real databases.
I’ve been playing with some ideas of applying Datalog to RDF graphs; there’s a very rough and ready implementation at https://github.com/alexchamberlain/mutant. This isn’t a new idea; Apache’s Marmotta is very similar.
I think we’ve really missed a trick with declarative programming beyond the database. I find it much easier to think about simple rules, and I think it would be easier to share these rules with less technical business partners too.
To be honest, I'm not 100% sure. The tooling that exists - at least in the open source space - seems to be vastly dominated by Java and academic endeavours. That being said, I think the ideas behind RDF are pretty awesome, and its simplistic structure makes full indexing, datalog inference and layering possible.
My research group (I'm a PhD student) is working on algorithms that learn
logic programs from examples and background knowledge (also given as logic
programs). The programs our algorithms learn are first order definite datalog
programs, which means they are sets of first order Horn clauses without
negation as failure and without any functions of arity more than 1 as
arguments of literals or terms.
The reason for the restriction is completeness and efficiency. Definite
datalog programs are guaranteed to terminate (given a finite predicate and
constant signature), so the search for a hypothesis (the learned program)
cannot "go infinite" even when the target theory (what you are trying to
learn) is recursive, even when it has mutually recursive clauses. As a result
our algorithms can learn recursive programs (which, is rather important). The
space of hypotheses doubles in size when negation as failure is allowed, which
improves the efficiency of the search for hypotheses.
The problem of course is that some programs cannot be expressed in definite
datalog than can be expressed in Prolog with negation as failure and arbitrary functions
as arguments. So that's a bit of a limitation. For instance, one has to jump
through hoops to learn programs with "exceptions" (A if B except if C), say
like a program calculating leap years (which have exceptions for years
divisible by 100 and 400) or fizzbuzz.
This is not directly programming with datalog- it's machine learning of datalog
programs from data. But I think it's similar to the experience you're asking
for.
My group's algorithms:
Metagol (a meta-interpretive learner for definite datalog programs):
So you're building a program that can learn to write datalog programs. Is it because datalog programs are tedious enough they should be automateable? Why this particular research direction?
> The space of hypotheses doubles in size when negation as failure is allowed, which improves the efficiency of the search for hypotheses.
That line confused me. Shouldn't a double in the search space decrease the efficiency of the search for the hypothesis?
Well, there's that. My intuition is that ILP should appeal to computer scientists more than statistical machine learning. Unfortunately, it is not very widely known- we're a small field.
I am an more on the applied maths camp rather than the CS camp but I feel a practical and effective merger of logic and probabilistic reasoning is sorely needed to climb out of the rut we are in.
Neural Turing is all nice and dandy but it seems a very heavy handed way of expressing/learning dependencies.
The work I described falls under the category of Inductive Logic Programming,
a field at the intersection of machine learning and logic programming. In ILP
(as in logic programming) it's typical to restrict the expressivity of
first-order languages to improve efficiency and to guarantee termination.
Such restrictions often apply primarily to theoretical results, while in practice
there is more freedom. For example, my group's algorithms can learn normal
programs in practice, but our theoretical results only guarantee termination
(and so, learnability) of definite datalog programs.
In general, it takes a lot of work to find a representation language that is
expressive enough to allow learing of interesting and useful programs, and at
the same time, restricted enough to guarantee those programs _can_ be learned.
>> The space of hypotheses doubles in size when negation as failure is allowed,
which improves the efficiency of the search for hypotheses
I'm sorry if this was confusing. I meant that restricting hypotheses to
definite programs improves efficiency compared to allowing normal programs
(with negation as failure). The reason is that, if negation as failure is
allowed, in the worst case, an algorithm must consider both a literal and its
negation for inclusion in a clause, which doubles the cost of search for a
hypothesis.
21 comments
[ 5.9 ms ] story [ 34.6 ms ] threadSo Datalog is a better starting point, extend it in some other better ways than Prolog does.
However, Prolog predicates are relations, not functions. i.e. they have no fixed "input" and "output" arguments. So Prolog is not a functional language.
______________________
[1] In "p(X):- q(X)", p(X) and q(X) are literals.
I think we’ve really missed a trick with declarative programming beyond the database. I find it much easier to think about simple rules, and I think it would be easier to share these rules with less technical business partners too.
The reason for the restriction is completeness and efficiency. Definite datalog programs are guaranteed to terminate (given a finite predicate and constant signature), so the search for a hypothesis (the learned program) cannot "go infinite" even when the target theory (what you are trying to learn) is recursive, even when it has mutually recursive clauses. As a result our algorithms can learn recursive programs (which, is rather important). The space of hypotheses doubles in size when negation as failure is allowed, which improves the efficiency of the search for hypotheses.
The problem of course is that some programs cannot be expressed in definite datalog than can be expressed in Prolog with negation as failure and arbitrary functions as arguments. So that's a bit of a limitation. For instance, one has to jump through hoops to learn programs with "exceptions" (A if B except if C), say like a program calculating leap years (which have exceptions for years divisible by 100 and 400) or fizzbuzz.
This is not directly programming with datalog- it's machine learning of datalog programs from data. But I think it's similar to the experience you're asking for.
My group's algorithms:
Metagol (a meta-interpretive learner for definite datalog programs):
https://github.com/metagol/metagol
Louise (a polynomial-time version of Metagol):
https://github.com/stassa/louise
> The space of hypotheses doubles in size when negation as failure is allowed, which improves the efficiency of the search for hypotheses.
That line confused me. Shouldn't a double in the search space decrease the efficiency of the search for the hypothesis?
I am an more on the applied maths camp rather than the CS camp but I feel a practical and effective merger of logic and probabilistic reasoning is sorely needed to climb out of the rut we are in.
Neural Turing is all nice and dandy but it seems a very heavy handed way of expressing/learning dependencies.
The work I described falls under the category of Inductive Logic Programming, a field at the intersection of machine learning and logic programming. In ILP (as in logic programming) it's typical to restrict the expressivity of first-order languages to improve efficiency and to guarantee termination.
Such restrictions often apply primarily to theoretical results, while in practice there is more freedom. For example, my group's algorithms can learn normal programs in practice, but our theoretical results only guarantee termination (and so, learnability) of definite datalog programs.
In general, it takes a lot of work to find a representation language that is expressive enough to allow learing of interesting and useful programs, and at the same time, restricted enough to guarantee those programs _can_ be learned.
>> The space of hypotheses doubles in size when negation as failure is allowed, which improves the efficiency of the search for hypotheses
I'm sorry if this was confusing. I meant that restricting hypotheses to definite programs improves efficiency compared to allowing normal programs (with negation as failure). The reason is that, if negation as failure is allowed, in the worst case, an algorithm must consider both a literal and its negation for inclusion in a clause, which doubles the cost of search for a hypothesis.