SPARQL Algebra evaluation test coverage

Per my action [1] from the last teleconference: 

Below is a bit of what I had in mind with regards to having our SPARQL
test coverage criteria be driven by evaluation semantics as well as
grammar permutations.  The primary motivation is the fact that, at its
essence, the SPARQL algebra only consists of a handful of symbols and by
enumerating their various permutations you get decent coverage of the
evaluation semantics.  

In particular, after converting the abstract syntax tree to its
equivalent SPARQL algebra expression, each GroupGraphPattern can be
treated [2] as a list of expressions against which a fold [3] function
can be applied.  This significantly reduces the number of permutations
to consider as the (lambda) function supplied to fold takes only two
arguments.  

If you ignore FILTER expressions (for now), the left argument can only
be one of:

I.   LeftJoin(BGP(..),{..})
II.  Join(BGP(..),Graph(varOrIRI,{..}))
III. Join(BGP(..),Union(A,B))
IV.  Graph(varOrIRI,{..})
V.   LeftJoin({},{ .. }) - reduces to solutions for {}
VI.  Union(A,B)
VII. BGP(..)  <-- not accounted for

The right argument can only be one of the same with the exception of:

LeftJoin(<insert left argument>,{ .. })

Where the left argument can be an empty graph pattern ({}) or otherwise.
The first case is already covered, the second depends on what the left
argument is.  One such scenario (where the left argument is a BGP) is
already covered by I.

By themselves, most (if not all) of these forms are probably already
covered by previous tests.

When you consider the application of the fold function to be equivalent
to the Join operator (this follows from 12.2.1 Converting Graph
Patterns) then you get the following permutations (skipping various
simplifications and eliminating duplicates - for brevity).

1.  LeftJoin(LeftJoin(BGP(..),{ .. }),{ .. })
2.  LeftJoin({},{ .. })  - covered by V.
3.  Join(LeftJoin(BGP(..),{ .. }),LeftJoin(BGP(..),{ .. }))
4.  Join(LeftJoin(BGP(..),{ .. }),LeftJoin({},{ .. })) - covered by I.
5.  Join(LeftJoin(BGP(..),{ .. }),Union(A,B))
6.  LeftJoin(Join(BGP(..),Graph(varOrIRI,{..})),{ .. })
7.  Join(Join(BGP(..),Graph(varOrIRI,{..})),Union(A,B))
8.  LeftJoin(Join(BGP(..),Union(..)),{ .. })
9.  Join(Join(BGP(..),Union(..)),Union(A,B))
10.  LeftJoin(Graph(varOrIRI,{..})),{ .. })
11. Join(Graph(varOrIRI,{..})),Union(A,B))
12. LeftJoin(LeftJoin({},{ .. }), { .. })
13. LeftJoin(LeftJoin({},{ .. }), Union(A,B))
14. LeftJoin(BGP(..), { .. })
15. Join(BGP(..),Join(BGP(..),Union(A,B)))
16. Join(BGP(..),Join(BGP(..),Graph(varOrIRI,{..})))
17. Join(BGP(..),LeftJoin(BGP(..),{..}))
18. Join(BGP(..),BGP(..))
19. Join(BGP(..),Graph(varOrIRI,{..})) - covered by 6,7 
20. Join(BGP(..),Union(A,B)) - covered by 15

This is just a start and does not represent exhaustive coverage (neither
FILTERs nor solution modifiers were considered), but it gives a top
level criteria for test coverage of the evaluation semantics of the
SPARQL algebra.  I'm pretty sure a significant number of these forms are
already covered by existing tests.

[1] http://www.w3.org/2007/05/29-dawg-minutes.html#action09
[2] http://svn.rdflib.net/trunk/rdflib/sparql/Algebra.py 
[3] http://en.wikipedia.org/wiki/Fold_%28higher-order_function%29

-- 
Chimezie Ogbuji
Lead Systems Analyst
Thoracic and Cardiovascular Surgery
Cleveland Clinic Foundation
9500 Euclid Avenue/ W26
Cleveland, Ohio 44195
Office: (216)444-8593
ogbujic@ccf.org


===================================




Cleveland Clinic is ranked one of the top 3 hospitals in
America by U.S.News & World Report. Visit us online at
http://www.clevelandclinic.org for a complete listing of
our services, staff and locations.


Confidentiality Note:  This message is intended for use
only by the individual or entity to which it is addressed
and may contain information that is privileged,
confidential, and exempt from disclosure under applicable
law.  If the reader of this message is not the intended
recipient or the employee or agent responsible for
delivering the message to the intended recipient, you are
hereby notified that any dissemination, distribution or
copying of this communication is strictly prohibited.  If
you have received this communication in error,  please
contact the sender immediately and destroy the material in
its entirety, whether electronic or hard copy.  Thank you.

Received on Monday, 4 June 2007 13:56:25 UTC