1
$\begingroup$

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.

Thanks in advance.

Improve this question
$\endgroup$
4
  • $\begingroup$ I will happily elaborate on any terms if needed. $\endgroup$
    – Codey
    Feb 11, 2016 at 22:01
  • $\begingroup$ 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. $\endgroup$
    – vonbrand
    Feb 11, 2016 at 23:51
  • 2
    $\begingroup$ @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. $\endgroup$
    – David Richerby
    Feb 12, 2016 at 0:17
  • $\begingroup$ 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. $\endgroup$
    – Codey
    Feb 12, 2016 at 1:46

1 Answer 1

Reset to default
2
$\begingroup$

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

Improve this answer
$\endgroup$
1
  • $\begingroup$ This makes since. I felt like I just needed something concrete to look at to understand how it affects the data. My only other question would be can this operator be performed once, or must is always be performed in iterations like you have shown? And say the question was: what is the outcome of Tp(p(a)) performed with the rules and facts listed above would the outcome be {p(a), q(a). Of course, I can easily see why the iterative approach has some application. $\endgroup$
    – Codey
    Feb 11, 2016 at 22:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.