# Questions tagged [datalog]

The tag has no usage guidance.

7 questions
Filter by
Sorted by
Tagged with
106 views

### Conjunctive Query Containment as SAT

The problem of conjunctive query containment is known to be NP-Complete (originated at Chandra&Merlin 1977). Typically it's shown by reducing 3SAT or 3-colorability into this problem, and the ...
61 views

### How to describe Deterministic Transitive Closure in FOL?

In "Finite Model Theory and Its Applications", page 152, it is said that Deterministic Transitive Closure, on ordered finite structures, captures LOGSPACE. Hence, taking into account that ...
68 views

### Datalog Program Equivalence with Fixed Universe Size

It is well known that to compute equivalence of two Datalog programs (or equivalently of two first order formulas with the least fixed point operator) wrt all possible inputs and universes, is ...
243 views

### Datalog Self Interpretation

According to https://link.springer.com/article/10.1007%2Fs001530050135 (Logics that define their own semantics, Imhof 1999) the logic FO[LFP] can define its own semantics, though the proof (of ...
147 views

### Is Datalog negation and the built-in predicate $\neq$ similar?

I was reading "Principles of Database & Knowledge-Base Systems, Vol. 1" by Jeffrey D. Ullman. There is a chapter about Datalog negation and as I was seeing the problems of negation I kept thinking ...
207 views

### Detect non existence of a cycle in a graph using Datalog : SMTLIB Format for Z3

I want to detect the non existence of a cycle in a graph using Datalog (which is a declarative logic programming language). The proposed solution was: ...
41 views

### Datalog maintaining views incrementally with negation

Given a single IDB rule $$R(x) \ \mathop{:\!\!-} \ A(x), \lnot B(x)$$ Where $A$ and $B$ are EDB predicates, how would I go about calculating changes to $R$ as tuples are added to $B$? As I ...