SPARQL Graph Pattern comparison

Question

A SPARQL Graph Pattern is a conjunction of triple patterns of the form UBVxUVxUBVL. Where U is URI, B is a Blank Node V is a variable and L is a Literal.

Example:

Query q1

Select ?author where
?author ex:wrote ?book

Query q2

Select ?author where
?author ex:wrote ?book
?book ex:title "Eaters of the dead"

What is the best algorithm to compare the two basic graph patterns? For instance, results for the graph pattern of q2 are a subset of those for q1. How could I programmatically determine this?

Answer 1

You might be able to pull off what you're trying by converting the where clause into a graph. Then you can use standard graph algorithms to compare the queries, like using isomorphism to see if they're the same one.

Answer 2

The more specific pattern should return a smaller result set if q2 is part of q1. Therefore counting the two sets and subtracting count(q2) from count (q1) will show the number of authors in q1 which are not in q2, showing that q2 is more specific. If the result is negative, then Q2 was more specific.

For example:

 SELECT ((?countQ1 - ?countQ2) as ?result) WHERE {

       {SELECT (count(distinct ?author) as ?countQ1) WHERE {
              ?author ex:wrote ?book .
       }}

       {SELECT (count(distinct ?author) as ?countQ2) WHERE {
              ?author ex:wrote ?book .
              ?book ex:title "Eaters of the dead"
       }}
 }