import sys
from gastrodon import *
from rdflib import *
import pandas as pd
pd.options.display.width=120
pd.options.display.max_colwidth=100

"""
Explanation: <img src="img/tote_board.jpg">
Inference Over RDF Containers
Introduction
In a <a href="http://ontology2.com/notebooks/local/RDFContainers.html">previous</a> notebook,  I demonstrated queries and operations over RDF Containers,  one of two ways to represent ordered lists in RDF.
This work is motivated by my <a href="http://ontology2.com/essays/PropertiesColorsAndThumbnails.html">analysis of XMP data</a> found on my computer.  XMP data uses Containers heavily,  so I need ways to work with them that roll off my fingers.  I felt the queries in the <a href="http://ontology2.com/notebooks/local/RDFContainers.html">last notebook</a> were a little more complex than they needed to be,  so in this notebook I explore the use of inference to simplify queries and show a set of example queries that illustrate patterns for making queries against RDF Containers.
Inference is,  at root,  a simple concept.  Given some set of facts,  we can infer more facts.  In the case of RDF Containers,  we might have the fact that
?list rdf:_7 ?member .
and can infer that
?list rdfs:member ?member .
This makes it easy to write a query such as "what lists is ?member a ?member of".  This particular example is simple and mechanical,  but more complex inference rules are used in business rules engines to answer questions such as "can we ship this product to that customer?" or "will we extend credit to this customer?"
This notebook works an example end to end,  including

how to write queries over RDF Containers without inference
two inference rules that simplify queries over RDF Containers
a simple inference engine based on SPARQL
a discussion of more complex inference engine
a cookbook of queries over RDF Containers

Setup
Here I import the libraries that I use and configure Pandas.
End of explanation
"""


races=inline(r"""
@prefix rdf: <http://www.w3.org/1999/02/22-rdf-syntax-ns#> .
@prefix : <http://example.com/> .

:tioga_downs_2017_08_14 
    a rdf:Seq ;          
    rdf:_1 :race_1 ;                
    rdf:_2 :race_2 ;                
    rdf:_3 :race_3 .                
                                    
:race_1 
    a rdf:Seq ;
    rdf:_1 "PRINCE ADIRAN" ;        
    rdf:_2 "KDMAKEWAY" ;            
    rdf:_3 "ANDERSON VALLEY" ;      
    rdf:_4 "SETTINEMONFIRE" ;       
    rdf:_5 "TRILLIONAIR" ;          
    rdf:_6 "OZZY BLUE CHIP" .       
                                    
:race_2 
    a rdf:Seq ;                            
    rdf:_1 "MACHMEMACKIE" ;         
    rdf:_2 "FREE LOVE" ;            
    rdf:_3 "FRANKIES DRAGON" ;      
    rdf:_4 "IM AN ART MAJOR" ;      
    rdf:_5 "GOLD STAR SPIKE" ;      
    rdf:_6 "F TWENTY TWO" ;         
    rdf:_7 "TAILGUNNER HANOVER".    
                                    
:race_3 ; 
    a rdf:Seq ;                           
    rdf:_1 "LYONS JOHNNY" ;         
    rdf:_2 "BETTORSLUCKYSTREAK" ;   
    rdf:_3 "DASH OF DANGER" ;       
    rdf:_4 "NEPTUNE" ;               
    rdf:_5 "WINYARD HANOVER" ;       
    rdf:_6 "DEE'S ROCKETMAN" .                                           
""")

"""
Explanation: A Day at the races
Next I load a small data set to run test queries against:
End of explanation
"""


races.select("""
SELECT ?horse {
    :tioga_downs_2017_08_14  ?p1 ?race .
    ?race ?p2 ?horse .
    FILTER(STRSTARTS(STR(?p1),"http://www.w3.org/1999/02/22-rdf-syntax-ns#_"))
    FILTER(STRSTARTS(STR(?p2),"http://www.w3.org/1999/02/22-rdf-syntax-ns#_"))
}
""")

"""
Explanation: These come from the race results on August 14, 2017 at the Tioga Downs harness racing track.  This is not an example of a great
RDF representation of this kind of data,  but data structures like this are often used in scripty programs written in languages such as Python and Lisp.  If you want to imagine what a better representation looks like,  take a look at the source material:
<img src="race_results.png">
Queries without inference
Suppose we wanted to get a list of all race entries in all races.  The following query does the trick:
End of explanation
"""


def rule_1(endpoint):
    endpoint.update("""
        INSERT { 
            ?p a rdfs:ContainerMembershipProperty .
        } WHERE { 
            ?s ?p ?o .
            FILTER(REGEX(STR(?p),"^http://www[.]w3[.]org/1999/02/22-rdf-syntax-ns#_[1-9]([0-9])*$"))
        }
    """)
    
rule_1(races)

"""
Explanation: There are two things that bother me about this query:

It has a long,  arbitrary-looking,  hard to remember, and error prone FILTER clause for each container I want to traverse (what if I cut and pasted it and it was ?p1 both times)
It is not so obvious in this query,  but FILTER statements can occur only after all of the "basic graph patterns" (ex. ?s ?p ?o .) so the FILTER statements may have to be far away from the predicates they control,  making complex queries all the more complex and mysterious

The good news is that the RDF Schema specification already specifies a few inference rules to simplify this kind of query:
What is inference?
RDF Inference is a process in which we have some facts,  and then apply some rules to those facts to get more facts.  Inference addresses some of the problems solved by triggers and views in relational databases.  Inference is implemented in two ways:

In the case of Forward Chaining,  we compute the new facts and insert them in the database so that they will be seen by the query procedure.  (This is like a trigger in SQL)
In the case of Backward Chaining we rewrite the query or change the query answering procedure so that the new facts appear to be there.  (This is like a view in SQL)

RDFS Schema contains a number of features that are implemented with rules.  Often we're not interested in all of the possible inferences,  in which case we can implement the rules with a simple "inference engine" we write ourselves.
rdfs:ContainerMembershipProperty
The ContainerMembershipProperty class provides a quick way to select any predicate which denotes membership in a container.  According to the standard,
<div style="margin-left: 11px">
    Excerpt of <a href="http://www.w3.org/TR/rdf-schema/#ch_containermembershipproperty">Section 5.1.5 of the RDF Schema specification</a>
</div>

<div style="border: 1px solid black; margin: 5px; padding: 5px;">
<section id="ch_containermembershipproperty" typeof="bibo:Chapter" resource="#ref" rel="bibo:Chapter">
          <p>The <code>rdfs:ContainerMembershipProperty</code> class has as
            instances
            the properties <code>rdf:_1, rdf:_2, rdf:_3 ...</code> that are
            used to state
            that a resource is a member of a container.
            <code>rdfs:ContainerMembershipProperty</code> is a <a href="#def-subclass">subclass</a>
            of <a href="#ch_property"><code>rdf:Property</code></a>. Each
            instance of
            <code>rdfs:ContainerMembershipProperty</code> is an <a href="#ch_subpropertyof"><code>rdfs:subPropertyOf</code></a>
            the <code><a href="#ch_member">rdfs:member</a></code> property.</p>
          <p>Given a container C, a triple of the form:</p>
          <blockquote> <code>C rdf:_nnn O</code>
          </blockquote>
          <p>where <code>nnn</code> is the decimal representation of an integer
            greater than 0 with
            no leading zeros, states that O is a member of the container C.</p>
          <p>Container membership properties may be applied to resources other
            than containers.</p>
        </section>
</div>

The term rdfs:subPropertyOf is important in the above definition and is defined as follows:
<div style="margin-left: 11px">
    Excerpt of <a href="http://www.w3.org/TR/rdf-schema/#ch_containermembershipproperty">Section 3.5 of the RDF Schema specification</a>
</div>

<div style="border: 1px solid black; margin: 5px; padding: 5px;"> 

<section id="ch_subpropertyof" typeof="bibo:Chapter" resource="#ref" rel="bibo:Chapter">
        <p>The property <code>rdfs:subPropertyOf</code> is an instance of <code><a href="#ch_property">rdf:Property</a></code> that is used to state
          that all resources related by one property are also related by
          another.</p>
        <p>A triple of the form:</p>
        <blockquote> <code>P1 rdfs:subPropertyOf P2</code>
        </blockquote>
        <p>states that P1 is an instance of <code><a href="#ch_property">rdf:Property</a></code>,
          P2 is an instance of <code><a href="#ch_property">rdf:Property</a></code>
          and P1 is a <a href="#def-subproperty">subproperty</a> of P2. The
          <code>rdfs:subPropertyOf</code> property is transitive.</p>
        <p>The <a href="#ch_domain"><code>rdfs:domain</code></a> of
          <code>rdfs:subPropertyOf</code> is <code><a href="#ch_property">rdf:Property</a></code>.
          The <a href="#ch_range"><code>rdfs:range</code></a> of
          rdfs:subPropertyOf is <a href="#ch_property"><code>rdf:Property</code></a>.</p>
      </section>
</div>

Putting together the two definitions and thinking about it,  I get the idea that we can implement ContainerMembershipProperty by
writing the following production rule in psuedocode,  where I use regular expression symbols to formalize the rdf:_nnn idea in 
    the definition above.
IF 
        ?s ?p ?o .
        AND ?p MATCHES :rdf_[1-9]([0-9])* 
    THEN
       ?p a :ContainerMembershipProperty
There is not a well-standardized way to write production rules in RDF,  but we can easily write a SPARQL query that implements this,  at the cost of reversing the order of the IF and THEN clauses:
End of explanation
"""


races.select("""
    SELECT ?p { 
        ?p a rdfs:ContainerMembershipProperty .
    } ORDER BY ?p
""")

"""
Explanation: To see what this entails,  I run the following query:
End of explanation
"""


races.select("""
SELECT ?horse {
    :tioga_downs_2017_08_14  ?p1 ?race .
    ?p1 a rdfs:ContainerMembershipProperty .
    ?race ?p2 ?horse .
    ?p2 a rdfs:ContainerMembershipProperty .
}
""")

"""
Explanation: And I can now write a query for "all race entries" that is a little more sensible:
End of explanation
"""


def rule_2(endpoint):
    endpoint.update("""
        INSERT { 
            ?container rdfs:member ?member .
        } WHERE { 
            ?container ?containerMembershipProperty ?member .
            ?containerMembershipProperty a rdfs:ContainerMembershipProperty .
        }
    """)
    
rule_2(races)

"""
Explanation: Let's talk about entailment
Here's an issue which may seem a little strange,  but it is fundamental to the use of logic to solve problems in computing.
We know,  for instance,  that
rdf:_179426083 a rdfs:ContainerMembershipProperty .
and this is true for every integer greater than zero,  that is,  one way of thinking about it,  the ContainerMembershipProperty entails an infinite number of facts!
It's not at all conceivable that we could materialize an infinite number of facts if we were forward chaining.  It would not only take an infinite amount of time, but it would take an infinite amount of space.
What's less obvious is that if we implemented the ContainerMembershipProperty rule inside the SPARQL engine,  it is just as unreasonable to generate an infinite number of rows by writing a query like
SELECT ?p { 
    ?p a rdfs:ContainerMembershipProperty .
} ORDER BY ?p
even though this looks much like writing
count=0
while True:
    print(count)
    count+=1
in Python,  which is possible,  if ill-advised.  (There is a reason why I am embedding that code in a Markdown block instead of running it in a code block!)
It turns out that SPARQL,  SQL and most other query languages only allow bounded loops,  so that it is impossible to write a program that runs forever.  This is opposed to a Turing-complete language such as Python in which one can write more expressive programs at the cost of possibly writing a program which never terminates.  (See the Halting Problem if you wish to learn more.)
This kind of issue is addressed by defining an entailment regime;  for instance,  to answer any query where 
?p a rdfs:ContainerMembershipProperty .
has a ?p that matches a resource in a query pattern,  we only need to materialize those facts for predicates that actually occur in the graph,  as opposed to those which could match any possible statement.
rdfs:member
The rdfs:member property connects each container to all of its members.  It is defined like so:
<div style="margin-left: 11px">
    Excerpt of <a href="http://www.w3.org/TR/rdf-schema/#ch_containermembershipproperty">Section 5.1.6 of the RDF Schema specification</a>
</div>

<div style="border: 1px solid black; margin: 5px; padding: 5px;">
  <p><code>rdfs:member</code> is an instance of <code><a href="#ch_property">rdf:Property</a></code>
    that is a super-property of all
    the container membership properties i.e. each container membership
    property
    has an <a href="#ch_subpropertyof"><code>rdfs:subPropertyOf</code></a>
    relationship to the property <code>rdfs:member</code>.</p>
</div>

I can implement that rule with the following SPARQL query
End of explanation
"""


races.select("""
   SELECT DISTINCT ?list {
       ?list rdfs:member ?member .
   }
""")

"""
Explanation: Then I can write a very simple query that finds all of the non-empty containers in the graph
End of explanation
"""


def container_inference(endpoint):
    rule_1(endpoint)
    rule_2(endpoint)

"""
Explanation: About inference engines
Simple Inference
I can put the two rule definitions together to make a simple inference engine:
End of explanation
"""


def rule_t(endpoint):
    endpoint.update("""
        INSERT { 
            ?self rdfs:subClassOf ?grandparent .
        } WHERE { 
            ?self rdfs:subClassOf ?parent .
            ?parent rdfs:subClassOf ?grandparent .
        }
    """)

"""
Explanation: This inference engine works because that:

A fact generated by either rule1 or rule2 cannot change the result of rule1
A fact generated by either rule2 cannot change the result of rule2

Thus I can evaluate the rules in sequence and know that I am done.  Also the relationship between the rules is simple,  so it's easy for me to figure out the right order to evaluate them in.
If I add some facts to the graph,  run the engine,  add some more facts,  and run the engine again,  that is also OK,  because the act of adding facts to the graph is idempotent.
The Fixed Point Algorithm
What I'm doing is closely related to SPIN rules,  in fact,  SPIN rules are a set of SPARQL update statements that are repeated over and over again until the graph stops changing.
In the case above,  for instance,  if I got the order of the rules wrong,  repeating the inference process to a fixed point would give the same answer as the rules below.  It might take a little more time,  but the rule author doesn't need to think so much.
Another case for the fixed point algorithm is a rule like:
End of explanation
"""


races.select("""
    select (count(*) as ?count) {
       :race_2 rdfs:member ?member
    }
""")

"""
Explanation: which makes rdfs:subClassOf a transitive property.  Because it generates new rdfs:subClassOf statements,  running the rule again can generate more facts.  It never makes an infinite loop however,  since it is triggered by a finite number of statements in the graph.  Even if I abuse it by making the graph have a cycle,  the iteration stops because,  after a while,  the rule is inserting the same facts into the graph over and over again,  which is a non-operation.
RETE and friends
In the case of the simple inference engine,  I can work out in my head which rules can cause which other rules to fire,  thus put them in the right order.
The RETE algorithm,  and variations of the RETE algorithm,  does this automatically,  compiling a network of matching conditions that could apply to incoming facts,  thus only checking the rules that have a chance to fire.
A few examples of RETE-related rules engines are

Drools
JESS
IBM Operational Decision Management
The Jena Rules Engine
PyCLIPS
Clara
FuXi

RETE engines are particularly good for complex event processing and workflow engines workflow as the RETE engine works incrementally,  firing rules as they become applicable.  Thus the rules can be as valuable for the side effects they generate as they are for the facts they imply.
Truth Maintainance
With the container_inference procedure there would be a problem if I deleted facts from the graph,  because the system would not know it is supposed to delete rdfs:member statements that were implied by the deleted facts.  In this case the problem is solved because I insert the data,  do the inference,  make queries and never delete any statements.
Really advanced rules engines (many of the ones listed above) combine the RETE algorithm with a Truth Maintainance System which automatically retracts inferred statements when the facts that imply them are removed.
Backwards chaining
It is also possible to perform inference by backwards chaining,  when you start with a query you'd like to solve,  and the query processing engine executes the query to pretend that the inferred facts exist.  Prolog is an example of a logic programming language based on backwards chaining.  Datalog is a subset of Prolog that applies to database systems,  because,  like a SPARQL query,  Datalog programs are guaranteed to terminate.
In the case discussed here,  rdfs:member and rdfs:ContainerMembershipProperty could be implemented in a SPARQL query by rewriting a query like
SELECT ?p {
 ?p a rdfs:ContainerMembershipProperty .
}
to
SELECT ?p {
 ?s ?p ?o .
 FILTER(REGEX(STR(?p),"^http://www[.]w3[.]org/1999/02/22-rdf-syntax-ns#_[1-9]([0-9])*$"))
}
and this would be an example of backwards chaining inference.  Both RDFS and OWL are designed such that most rule sets can be executed efficiently by either backwards or forward chaining.
Queries over Containers with Inference
Counting unique members
A count of unique members can easily be made with the following query:
End of explanation
"""


duplicates=inline(r"""
@prefix rdf: <http://www.w3.org/1999/02/22-rdf-syntax-ns#> .
@prefix : <http://example.com/> .

:three_cheers
    a rdf:Seq ;
    rdf:_1 "cheer!" ;
    rdf:_2 "cheer!" ;
    rdf:_3 "cheer!" .
""")

container_inference(duplicates)

duplicates.select("""
    select (count(*) as ?count) {
       :three_cheers rdfs:member ?member
    }
""")

"""
Explanation: note that this a count of unique members as opposed to a count of members.  This can be seen with the following test data:
End of explanation
"""


duplicates.select("""
    select ?s ?p ?o {
       ?s ?p ?o .
       FILTER(?p=rdfs:member)
    }
""")

"""
Explanation: What happened here is that the facts in an RDF graph have set semantics,  so the fact
:three_cheers rdfs:member ?member .
only occurs once,  no matter how many container membership properties link those two facts:
End of explanation
"""


duplicates.select("""
    select (count(*) as ?count) {
       :three_cheers ?p ?member .
       ?p a rdfs:ContainerMembershipProperty
    }
""")

races.select("""
    select (count(*) as ?count) {
       :race_2 ?p ?member .
       ?p a rdfs:ContainerMembershipProperty
    }
""")

"""
Explanation: Counting all members
it takes a slightly different query to count all members:
End of explanation
"""


races.select("""
    select ?horse {
       :tioga_downs_2017_08_14 rdfs:member/rdfs:member ?horse
    }
""")

"""
Explanation: Queries involving property paths
Container membership inference helps us take advantage of property paths in SPARQL to simplify queries.  For example,  consider:
End of explanation
"""


races.select("""
    select ?horse {
       :tioga_downs_2017_08_14 rdf:_3/rdf:_4 ?horse .
    }
""")

"""
Explanation: to get a list of all unique horses that ran.  This is the same as "all race entries" because a specific horse runs at most once a day.
Fourth horse in the third race?
Property paths are just peachy for the case where we want to index specific nested members
End of explanation
"""


races.select("""
    select ?horse {
       "F TWENTY TWO" ^rdfs:member/rdfs:member ?horse
    }
""")

"""
Explanation: Queries involving inverse property paths
This query takes advantage of ^ reversing the direction of a property in a property path to get "horses that ran in the same race as F TWENTY TWO"
End of explanation
"""


races.select("""
    select ?member {
       :tioga_downs_2017_08_14 rdfs:member+ ?member
    }
""")

"""
Explanation: Queries with variable-length property paths
We can recursively descend through members of a list like so:
End of explanation
"""


races.select("""
    select (COUNT(*) AS ?count) {
       :tioga_downs_2017_08_14 ?p1 [ ?p2 ?horse] .
       ?p1 a rdfs:ContainerMembershipProperty.
       ?p2 a rdfs:ContainerMembershipProperty .
    }
""")

"""
Explanation: This gives us the members of :tioga_downs_2017_08_14;  all of those are lists,  so we also get the members of those lists.
another shorthand for paths
Steps of property paths have to be literal URIs,  not variables.  Paths involving variables can be written with the [ ] shorthand.  The following query counts all of the race entries,  which is the same as the number of horses in this case:
End of explanation
"""


races.select("""
    select ?race ?win ?place ?show {
       ?race
           ^rdfs:member :tioga_downs_2017_08_14 ;
           rdf:_1 ?win ;
           rdf:_2 ?place ;
           rdf:_3 ?show .
    }
""")

"""
Explanation: Who finished in the money?
In this case,  the inverse property path makes for a short and sweet query
End of explanation
"""


duplicates.select("""
    select ?list (count(*) as ?count) {
       ?list rdfs:member ?member.
    } GROUP BY ?list
""")

"""
Explanation: Distinct counts (for a set of Containers)
GROUP BY can be used to count over more than one container.  The following counts distinct members:
End of explanation
"""


races.select("""
    select ?race (count(*) as ?count) {
       ?race 
            ^rdfs:member :tioga_downs_2017_08_14 ;
             rdfs:member ?horse
    } GROUP BY ?race
""")

"""
Explanation: In the above case there is one result because there is just one container,  but if there are multiple containers,  this pattern gives multiple results:
End of explanation
"""


duplicates.select("""
    select ?list (count(*) as ?count) {
       ?list ?p ?member.
       ?p a rdfs:ContainerMembershipProperty .
    } GROUP BY ?list
""")

races.select("""
    select ?race (count(*) as ?count) {
       ?race 
            ^rdfs:member :tioga_downs_2017_08_14 ;
            ?rdfN ?horse .
       ?rdfN a rdfs:ContainerMembershipProperty . 
    } GROUP BY ?race
""")

"""
Explanation: List of (not) distinct counts
If the members of the container are not unique,  some occur multiple times,  and the count of members is greater than the distinct member count. This query counts multiple occurences of members.
End of explanation
"""


races.select("""
    select ?race {
        {
            select ?race (count(*) as ?count) {
               ?race 
                    ^rdfs:member :tioga_downs_2017_08_14 ;
                    ?rdfN ?horse .
               ?rdfN a rdfs:ContainerMembershipProperty . 
            } GROUP BY ?race
        }
        FILTER(?count=6)
    }
""")

"""
Explanation: Find containers with a certain number of distinct members
This query involves a subquery.  Subqueries in SPARQL are very general;  most queries you can imagine can be done with subqueries in SPARQL.
This example is simple,  using the subquery mechanism to accomplish something like the HAVING clause in SQL.  I put the query immediately above into another query which filters for a containers of length 6.
End of explanation
"""


races.select("""
    select ?race ?length {
        :tioga_downs_2017_08_14 rdfs:member ?race .
        {
            select (count(*) as ?length) {
                ?race rdfs:member ?horse
            }
        }
    }
""")

"""
Explanation: Counting with a subquery
Some people might find the "list of counts" examples to be awkward because what is done in one place in many programming languages (ex. Python)
len(some_list)
as opposed to (1) an aggregate operation in the select clause of the query,  (2) a pattern involving rdfs:member or rdfs:ContainerMembershipProperty) and (3) a GROUP BY clause.  A subquery can bring these elements closer together,  like so:
End of explanation
"""


