This slides were made for the presentation of the Master Thesis of Guido Naudts with the aim of obtaining the degree of engineer in software science. The coaching and graduation committee was composed as follows: The main goal of the thesis was to study inferencing in connection with RDF, the Resource Description Framework, a standard of the W3C (World Wide Web Center).

Before discussing the specific research goals, the globalcontext of the research is discussed using a case study. A travel agent in Antwerp has a client who wants to go to St.Tropez in France. There are rather a lot of possibilities for composing such a voyage. The client can take the train to France, or he can take a bus or train to Brussels and then the airplane to Nice in France, or the train to Paris then the airplane or another train to Nice. The travel agent explains the client that there are a lot of possibilities. During his explanation he gets an impression of what the client really wants. The travel agent agrees with the client about the itinerary: by train from Antwerp to Brussels, by airplane from Brussels to Nice and by train from Nice to St. Tropez. This still leaves room for some alternatives. The client will come back to make a final decision once the travel agent has said him by mail that he has worked out some alternative solutions like price for first class vs second class etc... Remark that the decision for the itinerary that has been taken is not very well founded; only very crude price comparisons have been done based on some internet sites that the travel agent consulted during his conversation with the client. A very cheap flight from Antwerp to Cannes has escaped the attention of the travel agent. The travel agent will now further consult the internet sites of the Belgium railways, the Brussels airport and the France railways to get some alternative prices, departure times and total travel times. Now let’s compare this with the hypothetical situation that a full blown Semantic Web would exist. In the computer of the travel agent resides a Semantic Web agent that has at its disposal all the necessary standard tools. The travel agent has a specialised interface to the general Semantic Web agent. He fills in a query in his specialised screen. This query is translated to a standardised query format for the Semantic Web agent. The agent consult his rule database. This database of course contains a lot of rules about travelling as well as facts like e.g. facts about internet sites where information can be obtained. There are a lot of ‘path’ rules: rules for composing an itinerary.  The agent contacts different other agents like the agent of the Belgium railways, the agents of the French railways, the agent of the airports of Antwerp, Brussels, Paris, Cannes, Nice etc... With the information received its inference rules about scheduling a trip are consulted. This is all done while the travel agent is chatting with the client to detect his preferences. After some 5 minutes the Semantic Web agent gives the travel agent a list of alternatives for the trip; now the travel agent can immediately discuss this with his client. When a decision has been reached, the travel agent immediately gives his Semantic Web agent the order for making the reservations and ordering the tickets. Now the client only will have to come back once for getting his tickets and not twice. The travel agent not only has been able to propose a cheaper trip as in the case above but has also gained an important amount of time.

An RDF file is a set of triples. A triple is composed of a subject, a predicate and an object. A triple can be a fact or a rule. The notation that is used is a prolog-like syntax where variables are indicated by capitals and constants start with a miniscule. This rule says that, if X is a child of Y and Y is a child of Z then Z is a grandparent of X.

In this slide some aspects are discussed that are typical for the Semantic Web and that an reasoning engine for RDF has to take into account. as was shown in the case study, it must be possible for the inferencing program to direct queries to other sites and get answers in return. databases and results must be verifiable i.e. it must be necessary to check whether a RDF triple can be accepted or not. The link with the trust system is obvious. Verifiability/trust points also to the necessity of keeping track of the origin off all triples and within a triple of its labels (not all labels of a triple are necessarily originating from the same site). While recieving information from many different sites, the danger of inconsistency is higher as in a stand-alone application.

This slide represents the structure of the reasoning program. The upper blocks represent the input. All input is put in a concrete RDF syntax like the one shown in a previous slide; other syntaxes are e.g. Notation 3 and the graph syntax. The first block contains metarules: these are general rules that can be used by a set of applications. This block might also contain rules for ontologies. The first of the middle blocks represents the reasoning kernel of the program. It uses an abstract RDF syntax (for this thesis specified in Haskell). This block can direct a query to another site (second block in the middle) and recieve a response. The lowest block represents the output (solutions and proofs of those solutions) of the program. The output is again in a  concrete RDF syntax.

This slide demonstrates the inner workings of the inferencing kernel. The mechanism used is ‘resolution based inferencing’ also called ‘backward reasoning’. The query is: grandmother(Z,X). The grandmother rule says that somebody is a grandmother when the person is a grandparent and his gender is female. We now have to find somebody who is a grandparent with gender female. Two new nodes are drawn in the search tree: Now some Z is a grandparent when (a certain) X is a child of (a certain Y) and Y is a child of Z. Two nodes are added again: child(X, Y) and child(Y, Z). Now no more rules can be applied. But the triple child(X,Y) can match with two facts. Lets first substitute X by christine and Y by elza to get: child(christine, elza). In the figure we see now that the node child(Y,Z) becomes: child(elza, Z). This means we have to find the parent Z of elza; but such fact is not in the database and therefore a cross is drawn over this goal. So the substitution that was done (X by christine and Y by elza) was no good. A backtrack must be done and another alternative has to be tried. Now we substitute X by wim and Y by christine.  The other child node no becomes: child(christine, Z) and we see that now Z can be susbtituted by elza and the node: gender(Z, female) now becomes gender(elza, female)  and this is confirmed by a fact in the database. So now we have found the solution: grandmother(elza, wim). The system will still try to find other solutions but none are found and inferencing terminates.

This slide show that the resolution based inference process can be represented in the form of a Finite State Machine (FSM). The ovals in the slide indicate the states; the rectangles are functions, that are executed when passing from state to another. Here follows an overview of all state changes. The proces starts with state 1 where the menu is displayed. Besides functions that are not shown in the figure, from the menu an inferencing process can be started by selecting a database and a query. In state 2 the data structures for the inferencing process are prepared and the query is entered in the goallist. Then the main state, 3, of the process is entered. a) the triple contains a builtin e.g. (Txxx, io:print, ”Message to the user”). Some following triples might also be used. After executing the builtin, the FSM will return to state 3.  b) the triple and a certain number of following triples define a subquery. The subquery is directed to another server. The returned results are integrated into the database and the FSM returns to state 3. c) the engine will take a goal and will try to match it with the database. One alternative is selected and added to the goallist and the other alternatives are pushed on the stack. If there were alternatives the FSM returns to state 3. If there were not, it goes to state 6. The program detects an empty goallist. This means all goals have been ‘proved’ and the resolution refutation process is complete. A solution has been found and the FSM passes to state 4. A solution has been found. The FSM passes control to the backtrack function that looks if alternatives are present on the stack for further investigation. If this is the case, then control is passed to state 5. The solve function tries to unify a goal with the database; however the unification process fails. The choose function detects the lack of alternatives and the FSM passes to state 6. The current search path is aborted.  The backtrack function looks for further alternatives; if this is the case, the FSM passes control to state 5. No more alternatives are present on the stack. The inferencing process is finished. The FSM passes to state 7. The inferencing process is finished. Results are displayed and/or used and control is passed to state 1.

An example of an open set is the set of all large internet sites e.g. all sites with more than 100.000 HTML pages. Characteristics of this set are: • it has no known limits (there exists of course a limit at any point in time but it is not known; for a computer this is the same as no limit). • if the existence of a universal quantifier is defined by the possibility of iteratively naming all elements of the set, then such a quantifier does not exist for an open set. A quantifier ‘for_all_those_known’ does exist. • the ‘law of excluded middle’ does apply: a person is either member of the club, or he is not. • it is possible to name iteratively all members of the club so a universal quantifier does exist.

The characteristics soundness and completeness of the program were proved by establishing a series of lemmas. These lemmas use reasoning on a graph as proof mechanism. I refer to my master thesis for more detail of these lemmas. Besides giving a proof of the soundness and completeness of the program, I was able to deduce from this theory: • under certain conditions it is possible to deduce a general rule (= procedure)  from a solution and its proof (shown in the demo).

The goal here is to compare ‘constructive logic’ with ‘first order logic’. Instead however of discussing logic systems the two logic systems are compared by means of an analogy in the three following slides. The constructive aspect here is that each triple in a proof (or a database) must be an existing triple i.e. the namespaces of the labels should exist, the notions expressed by the labels should be defined by the namespaces; the sites should be trusted; the origin of the triple should be a trusted site.

This famous drawing of Escher represents a building but a building that is impossible to build. In the analogy it represents first order logic. With first order logic it is possible to make definitions that are impossible to construct. where T1 and T2 are triples.  T1 might be true or T2 might be true but which one is true?? *  this is not an attack on first order logic: it is possible to make fine buildings too with first order logic; besides first order logic is a monument of science with huge merits, certainly in the field of mathematics.

This slide show how a general rule can be deduced from a solution and its proof. The precise technique is explained in the thesis text. As was shown in the slide with the search tree, a solution is found after following certain paths in a search tree. From the solution and its proof (as will be shown in the demo) it is possible to deduce a general rule with the form: A final remark: many other optimization techniques exist. Studying and testing some in relation with an RDF inference engine can be the subject of a next thesis.

For the treatment of inconsistencies the used logic system is important; remember that constructive logic leads to verifiable triples and the possibility of using the trust system. Though this priciple is valid for some constructive logic systems, for the WWW it is not wanted. For the treatment of inconsistencies (and errors) the trust system is important. In case of conflict, triples fom non-trusted sites can be thrown away (this can of course better be done preventively). At the present moment only theoretical conclusions can be made. The advent of an operational semantic web is necessary for seeing which inconsistencies will present themselves.

I return now to the case study of the beginning to make an evaluation of the program that was implemented for this thesis. The second version of the program can send a subquery and recieve an answer. It can also recieve a subquery and send an answer. So in order to have the program working on two sites that exchange queries, all that must be added is a (standard) IP client-server interface = 2 modules. In the case study the program works with large databases. I will suppose that those are relational databases. Then a module must be added that transforms a RDF query to a SQL query, makes the SQL query and transforms the result back to RDF. The transformation of a relational DB to RDF is straightforward: In order to make the inferencing that is necessary for this case study, a minimal number of builtins will have to be added to the program e.g. builtins for math, string, input and output.

The program was written using the Hugs interpreter that is compatible with Haskell 98. After starting winhugs and loading the program, the ‘start’ command is given.

child(Y,Z) where Y has to be susbtituted (or better 2$_$1?Y) by elza as you can see in the list of substitutions. So really, what is looked for is the mother of elza. But such a fact is not in the database as will appear from the next slide.

You can see now in the history that the engine has now used a different substitution for the triple child(X,Y) namely (see list of substitutions):

The list of substitutions gives all substitutions that were used in order to arrive at a solution. The facts that were found are shown and the used rules are instantiated (the variables are replaced with labels). Because the substitutions contain the level numbering the search tree can be reconstructed. A trace of the program is of course also a proof of a solution, but in this proof all failure paths of the search tree are missing and only the relevant (successful) paths are given. Also a general rule is deduced that permits to find a grandmother using only one rule.

In the used prolog-like notation for RDF the variables are universal variables with local scope. This means the scope is limited to one rule. If there are two rule e.g. It is clear that the ‘X’ and ‘Y’ of the first rule will not denote the same thing as the ‘X’ and ‘Y’ of the second rule. In order not to confuse variables all variables with local scope are transformed into variables with global scope. This is done by giving them a unique name. The unique name is made by prefixing the variables with ‘_n’ where n is a unique number for each rule.

In the slide above you can see that variables are prefixed with numbers followed by ‘$_$’. This is the ‘level numbering’. Suppose there is a rule: At one level in the inferencing process X is substituted by ‘John’ and at another level by ‘Peter’. Now there are two substitutions: Therefore, at each step in the inferencing proces variables are renamed by prefixing them with ‘n$_$’ where n is the number of the current level.