W3C home > Mailing lists > Public > public-rdf-dawg@w3.org > April to June 2006

ordering semantics of UNIONS and OPTIONALs

From: Eric Prud'hommeaux <eric@w3.org>
Date: Thu, 8 Jun 2006 04:33:04 +0200
To: Pat Hayes <phayes@ihmc.us>
Cc: public-rdf-dawg@w3.org
Message-ID: <20060608023304.GK13928@w3.org>

The objective of this message is to explore the complexity of
variables bound in OPTIONALs and UNIONs and used as constraints in
later OPTIONALs and UNIONs. My thesis is that in certain, detectable
situations, you get a factorial burden for finding the different
solutions that arise from the order being arbitary (and, in fact,
comprehensive).

In this, the metadata for ?:bookB has evolved over time from dc1.0 to
dc1.3 with different styles...

data:
  _:bookA bib:references _:bookB .
  _:bookB dc10:publisher <mailto:bob> .
  _:book10 dc10:publisher <mailto:bob> .
  _:bookB dc11:publisher <mailto:bob> .
  _:book11 dc11:publisher <mailto:bob> .
  _:bookB dc12:publisher [ foaf:name "Bob" ] .
  _:book12 dc12:publisher [ foaf:name "Bob" ] .
  _:bookB dc13:publisher [ foaf:name "Bob" ] .
  _:book13 dc13:publisher [ foaf:name "Bob" ] .

query:
  SELECT ?pub ?oth10 ?oth11 ?oth12 ?oth13
   WHERE { ?a bib:references ?b			   #
           OPTIONAL { ?b dc10:publisher ?pub .	   # 10
                      ?oth10 dc10:publisher ?pub } #
           ?a bib:references ?b
           OPTIONAL { ?b dc11:publisher ?pub .
                      ?oth11 dc11:publisher ?pub }
	   ?a bib:references ?b			   #
           OPTIONAL { ?b dc12:publisher ?pub .	   # 12
                      ?oth12 dc12:publisher ?pub } #
	   ?a bib:references ?b
           OPTIONAL { ?b dc13:publisher ?pub .
                      ?oth13 dc13:publisher ?pub }
         }

Pat, this scenario doesn't work yet, but maybe you can work out some
particular of when you will get different answers if you try the 10
pattern before the 11 pattern before the 12 pattern. Note: we need the
wierd repeated triples (or some triples) because while both of 11 and
12 can be processed an either order if they have a triple between the:

           ?a bib:references ?b			   #
           OPTIONAL { ?b dc11:publisher ?pub .	   # 11
                      ?oth11 dc11:publisher ?pub } #

	   ?a bib:references ?b			   #
           OPTIONAL { ?b dc12:publisher ?pub .	   # 12
                      ?oth12 dc12:publisher ?pub } #

without the extra triples:

           OPTIONAL { ?b dc11:publisher ?pub .	   # 11
                      ?oth11 dc11:publisher ?pub } #

           OPTIONAL { ?b dc12:publisher ?pub .	   # 12
                      ?oth12 dc12:publisher ?pub } #

One must process (get bindings from) 11 before 12.

Bonne chance,
-- 
-eric

home-office: +1.617.395.1213 (usually 900-2300 CET)
cell:        +81.90.6533.3882

(eric@w3.org)
Feel free to forward this message to any list for any purpose other than
email address distribution.
Received on Thursday, 8 June 2006 02:31:33 GMT

This archive was generated by hypermail 2.3.1 : Tuesday, 26 March 2013 16:15:26 GMT