3 ms·
I thought there was a big class of queries Datalog could not express -- something about negation, queries like "all X for which not Y". Is that not true? Or if
by Jeff_Brown 4y ago
I thought there was a big class of queries Datalog could not express -- something about negation, queries like "all X for which not Y". Is that not true? Or if it is, is Datalog somehow Turing complete nonetheless?
- zh217 4y agoTechnically, Cozo is using something called "Datalog with stratified negation, stratified aggregation, and function symbols", allowing aggregations to be auto-recursive when they form a semi-lattice, together with built-in algorithms which are black boxes taking in relations and giving you back another relation. Your example is taken care of by the "stratified negation" part. I believe "Datalog with function symbols" is already Turing complete, but you are right, what they call "Datalog" without any qualification in academic papers is not.