# Datalog - Single Step Operator

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.

• I will happily elaborate on any terms if needed. Feb 11 '16 at 22:01
• We can't read and explain the class material for you. If you have a specific question, that is not directly pertaining how to program. If it is about programming niceties, go to SO. Feb 11 '16 at 23:51
• @vonbrand Datalog is better thought of as a logic than a programming language. I think the question is on-topic, here. But I agree with your point about this not being a specific enough question. "Please explain this stuff to me in a different way" doesn't really work. It's already explained once and the asker's response was, "I don't get it." If somebody spends the considerable time needed to explain it again, there's a high chance that the response is, "I still don't get it." This is the sort of question that needs interactive responses and is best asked of the lecturer or TA. Feb 12 '16 at 0:17
• I understand what you guys are saying and I do apologize. As I mentioned in my comment under the accepted answer I was really looking for a concrete example I think is what my mind needed, because after seeing the operator use in a small defined case the it made much more since. I understand the material but I need to see how it worked in a specific example to really understand what the operator was doing. In my future questions I will try to narrow it down more. I appreciate the feed back. Feb 12 '16 at 1:46

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.
p(a).

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.)