home *** CD-ROM | disk | FTP | other *** search
/ Mac Easy 2010 May / Mac Life Ubuntu.iso / casper / filesystem.squashfs / var / lib / python-support / python2.6 / rdflib / sparql / bison / CompositionalEvaluation.pyc (.txt) < prev    next >
Encoding:
Python Compiled Bytecode  |  2009-04-20  |  5.0 KB  |  127 lines
  1. # Source Generated with Decompyle++
  2. # File: in.pyc (Python 2.6)
  3.  
  4. """
  5. This module implements (with sparql-p) compositional forms and semantics as outlined in
  6. the pair of Jorge P\xc2\xb4erez et. al papers:
  7.  
  8. - Semantics of SPARQL                (http://ing.utalca.cl/~jperez/papers/sparql_semantics.pdf)
  9. - Semantics and Complexity of SPARQL (http://arxiv.org/abs/cs.DB/0605124)
  10.  
  11. It also implements rewrite rules expressed in the SPARQL Algebra:
  12.  
  13. - http://www.w3.org/TR/rdf-sparql-query/#sparqlAlgebra
  14.  
  15. Compositional Semantics (Jorge P. et. al syntax)
  16.  
  17. == Definition 3.7 (Set of Mappings and Operations) ==
  18.  
  19. Omega1 and Omega2 are sets of mappings
  20.  
  21. I.   Omega1 \xe2\x8b\x89 Omega2          = {\xce\xbc1 \xe2\x88\xaa \xce\xbc2 | \xce\xbc1 \xe2\x88\x88 Omega1, \xce\xbc2 \xe2\x88\x88 Omega2 are compatible mappings } 
  22. II.  Omega1 \xe2\x88\xaa Omega2           = {\xce\xbc | \xce\xbc1 \xe2\x88\x88 Omega1 or \xce\xbc2 \xe2\x88\x88 Omega2 }
  23. III. Omega1 \\ Omega2           = {\xce\xbc1 \xe2\x88\x88 Omega1 | for all \xce\xbc\xe2\x80\xb2 \xe2\x88\x88 Omega2, \xce\xbc and \xce\xbc\xe2\x80\xb2 are not compatible }
  24. IV.  LeftJoin1(Omega1, Omega2) = ( Omega1 \xe2\x8b\x89 Omega2 ) \xe2\x88\xaa ( Omega1 \\ Omega2 ) 
  25.  
  26. NOTE: sparql-p implements the notion of compatible mappings with the 'clash' attribute
  27. defined on instances of _SPARQLNode (in the evaluation expansion tree)   
  28.  
  29. An RDF dataset is a set D = {G0, <u1,G1>,... <un,Gn>}
  30.  
  31. where G0, . . . ,Gn are RDF graphs, u1, . . . , un are IRIs, and n \xe2\x89\xa5 0.
  32.  
  33. NOTE: A SPARQL RDF dataset is equivalent to an RDFLib ConjunctiveGraph so we introduce
  34. a function rdflibDS(D) which returns the ConjunctiveGraph instance associated
  35. with the dataset D
  36.  
  37. Every dataset D is equipped with a function dD such that
  38. dD(u) = G if u,Gi \xe2\x88\x88 D and dD(u) = \xe2\x88\x85 otherwise
  39.  
  40. Let D be an RDF dataset and G an RDF graph in D
  41.  
  42. == Definition 3.9 (Graph Pattern Evaluation): ==
  43.  
  44. [[.]](D,G) Is the notation used to indicate the evaluation
  45. of a graph pattern.  
  46.  
  47. I.  [[(P1 AND P2)]](D,G)   = [[P1]](D,G) \xe2\x8b\x89 [[P2]](D,G)
  48. II. [[(P1 UNION P2)]](D,G) = [[P1]](D,G) \xe2\x88\xaa [[P2]](D,G)
  49. III.[[(P1 OPT P2)]](D,G)   = LeftJoin1([[P1]](D,G),[[P2]](D,G))  
  50. IV. If u \xe2\x88\x88 I, then 
  51.       [[(u GRAPH P)]](D,G)  = [[P]](D,dD(u))
  52.     if ?X \xe2\x88\x88 V , then
  53.       [[(?X GRAPH P)]](D,G) =
  54.         [[P]](D,G) \xe2\x8b\x89 { ?X -> rdflibDS(D).contexts(P) }
  55. V. [[(P FILTER R)]](D,G) = {\xce\xbc \xe2\x88\x88 [[P]](D,G) | \xce\xbc |= R}.
  56.  
  57. NOTE: RDFLib's ConjunctiveGraph.contexts method is used to append bindings
  58. for GRAPH variables.  The FILTER semantics are implemented 'natively'
  59. in sparql-p by python functions 
  60.  
  61. (http://dev.w3.org/cvsweb/2004/PythonLib-IH/Doc/sparqlDesc.html?rev=1.11#Constraini)
  62.  
  63. == Equivalence with SPARQL  Algebra (*from* DAWG SPARQL Algebra *to* Jorge.P et. al forms) ==
  64.  
  65. merge(\xce\xbc1,\xce\xbc2)             = \xce\xbc1 \xe2\x88\xaa \xce\xbc2
  66. Join(Omega1,Omega2)      = Filter(R,Omega1 \xe2\x8b\x89 Omega2)
  67. Filter(R,Omega)          = [[(P FILTER R)]](D,G)
  68. Diff(Omega1,Omega2,R)    = (Omega1 \\ Omega2) \xe2\x88\xaa {\xce\xbc | \xce\xbc in Omega1 \xe2\x8b\x89 Omega2 and *not* \xce\xbc |= R} 
  69. Union(Omega1,Omega2)     = Omega1 \xe2\x88\xaa Omega2 
  70.  
  71. #LeftJoin(Omega1,Omega2,R)= Filter(R,Join(Omega1,Omega2)) \xe2\x88\xaa Diff(Omega1,Omega2,R)
  72.  
  73. == Graph Pattern rewrites and reductions ==
  74.  
  75. [[{t1, t2, . . . , tn}]]D = [[({t1} AND {t2} AND \xc2\xb7 \xc2\xb7 \xc2\xb7 AND {tn})]]D
  76.  
  77. Proposition 3.13
  78.  
  79. The above proposition implies that it is equivalent to consider basic
  80. graph patterns or triple patterns as the base case when defining SPARQL general graph patterns.    
  81.  
  82. == BGP reduction and Disjunctive Normal Forms or Union-Free BGP ==
  83.  
  84. Step 5 of http://www.w3.org/TR/rdf-sparql-query/#convertGraphPattern
  85.     
  86. Replace Join({}, A) by A
  87. Replace Join(A, {}) by A
  88.  
  89. === Disjunctive Normal Form of SPARQL Patterns ==
  90.  
  91. See: http://en.wikipedia.org/wiki/Disjunctive_normal_form
  92.  
  93. From Proposition 1 of 'Semantics and Complexity of SPARQL'
  94.  
  95. I.  (P1 AND (P2 UNION P3)) \xe2\x89\xa1 ((P1 AND P2) UNION (P1 AND P3))
  96. II. (P1 OPT (P2 UNION P3)) \xe2\x89\xa1 ((P1 OPT P2) UNION (P1 OPT P3))
  97. III.((P1 UNION P2) OPT P3) \xe2\x89\xa1 ((P1 OPT P3) UNION (P2 OPT P3)) 
  98. IV. ((P1 UNION P2) FILTER R) \xe2\x89\xa1 ((P1 FILTER R) UNION (P2 FILTER R)) 
  99.  
  100. The application of the above equivalences permits to translate any graph pattern
  101. into an equivalent one of the form:
  102.  
  103. P1 UNION P2 UNION P3 UNION ... UNION P
  104.  
  105. NOTE: sprarql-p SPARQL.query API is geared for evaluation of SPARQL patterns already in DNF:
  106.  - http://dev.w3.org/cvsweb/~checkout~/2004/PythonLib-IH/Doc/Attic/pythondoc-sparql.html?rev=1.5&content-type=text/html;%20charset=iso-8859-1#sparql.SPARQL.query-method
  107.  
  108. """
  109.  
  110. def ReduceToDNF(ggp, prolog):
  111.     '''
  112.     From: Semantics of SPARQL
  113.     
  114.     [[{t1, t2, . . . , tn}]]D = [[({t1} AND {t2} AND \xc2\xb7 \xc2\xb7 \xc2\xb7 AND {tn})]]D
  115.     
  116.     Proposition 3.13
  117.     
  118.     The above proposition implies that it is equivalent to consider basic
  119.     graph patterns or triple patterns as the base case when defining SPARQL general graph patterns.    
  120.     '''
  121.     pass
  122.  
  123.  
  124. def CompositionalEvaluate(tripleStore, ggp, prolog, passedBindings):
  125.     pass
  126.  
  127.