# Datalog - Single Step Operator

Codey 09/23/2018 at 09:53. 1 answers, 0 views

I am currently taking a class called Logic for Computer Scientist. During the first four weeks or so now we have been studying a concept Datalog with subsections Syntax and Formal Semantics and Fixed-Point Semantics. In these weeks we have looked at several definitions atoms, ground atoms, herbrand interpretations, herbrand models, and herbrand base, and these concepts make complete since to me. We are currently looking at something called the Single Step Operator(Immediate Consequence Operator), and I am having a hard time understanding what it actually does. It appears to be in the form of a set builder notation which simply builds a set based of certain rules. This operator appears to take input and filter out some results based of the rules in the Definition of the Single Step Operator

I am looking to see if somebody can actually explain what this is doing. When it comes to understanding what the symbols mean I get it. But I can understand how exactly it affects the data being passed to it/used by it. If anybody has some guidance I would really appreciate it or any good links everything I have found on Google has the same sort of layout as what I show in the image so it doesn't offer any benefit to understanding the concept.

Derek Elkins 02/11/2016.

It's pretty straightforward from an operational perspective. It finds all the facts deduced by firing all the rules for exactly one round on the current database. Typically, you'll have $I_{n+1} = I_n \cup T_P(I_n)$ so that $I_n$ is a monotonically growing database.

Concretely, say you have the following rules and facts.

p(a).
q(X) :- p(X).
r(X) :- q(X).

Then the initial database is $I_0 = \{\mathtt{p(a)}\}$. $T_P(I_0) = \{\mathtt{q(a)}\}$, so $I_1 = \{\mathtt{p(a)}, \mathtt{q(a)}\}$. Then $T_P(I_1) = \{\mathtt{q(a)},\mathtt{r(a)}\}$ and $I_2 = \{\mathtt{p(a)}, \mathtt{q(a)},\mathtt{r(a)}\}$. Finally, $T_P(I_2) = \{\mathtt{q(a)},\mathtt{r(a)}\}$. At which point $I_3 = I_2$ which would be an implementation's signal to stop. (In my particular formulation I didn't include facts as consequences but you could do that as well. It's not clear if your definition treats facts as rules with empty heads.)