Re: disjunction implementation

On Mon, Jun 14, 2004 at 04:00:46PM -0500, Dan Connolly wrote:
> 
> On Fri, 2004-06-11 at 22:38, Eric Prud'hommeaux wrote:
> > I'm a dork. I sent out an optional arcs impelementation. I was supposed
> > to send disjunction implementation.
> 
> Specifically, w.r.t. 3.4 Subgraph Results
> http://www.w3.org/TR/2004/WD-rdf-dawg-uc-20040602/#r3.4
> 
> 
> I'm not sure I understand this. (more below...)
> 
> [...]
> > TEST CASE:
> > 
> >   ns <http://example.org/n#>
> >   assert (
> >    A0 p1 B .
> >   # A0 p2 C .
> >   # A0 p3 D .
> >   
> >   # A1 p1 B .
> >    A1 p2 C .
> >   # A1 p3 D .
> >   
> >   # A2 p1 B .
> >   # A2 p2 C .
> >    A2 p3 D .
> >   
> >   # A3 p1 B .
> >    A3 p2 C .
> >    A3 p3 D )
> >   
> >   ask (
> >    ( ?n p2 C || ?n p3 D ))
> >   
> >   collect (?n)
> > 
> > TEST RUN OUTPUT:
> > 
> > For W3C::Rdf::AlgaeCompileTree::UnionDisjunction:
> > 
> > +-------------------------+
> > |                        n|
> > |-------------------------|
> > |<http://example.org/n#A1>|
> > |<http://example.org/n#A3>|
> > |<http://example.org/n#A3>|
> > |<http://example.org/n#A2>|
> > +-------------------------+
> > or with "proofs"
> > +-------------------------+----------------------------------------------------+
> > |                        n|                                                    |
> > |-------------------------|----------------------------------------------------|
> > |<http://example.org/n#A3>|                                                    |
> > |<http://example.org/n#A3> <http://example.org/n#p2> <http://example.org/n#C> .|
> > |   -->{<file://na/home/eric/sources/public/perl/modules/W3C/Rdf/bin/run.sh>}  |
> > |------------------------------------------------------------------------------|
> > |<http://example.org/n#A1>|                                                    |
> > |<http://example.org/n#A1> <http://example.org/n#p2> <http://example.org/n#C> .|
> > |   -->{<file://na/home/eric/sources/public/perl/modules/W3C/Rdf/bin/run.sh>}  |
> > |------------------------------------------------------------------------------|
> > |<http://example.org/n#A2>|                                                    |
> > |<http://example.org/n#A2> <http://example.org/n#p3> <http://example.org/n#D> .|
> > |   -->{<file://na/home/eric/sources/public/perl/modules/W3C/Rdf/bin/run.sh>}  |
> > |------------------------------------------------------------------------------|
> > |<http://example.org/n#A3>|                                                    |
> > |<http://example.org/n#A3> <http://example.org/n#p3> <http://example.org/n#D> .|
> > |   -->{<file://na/home/eric/sources/public/perl/modules/W3C/Rdf/bin/run.sh>}  |
> > +-------------------------+----------------------------------------------------+
> 
> I don't understand this... answer. What we're looking for
> is the "the smallest subgraph that matches the query (i.e. the subgraph
> that gives the same results as the query on the original graph)" right?

I don't know. Maybe we want all the reasons to conclude a particular
solution. That seems easier to define. Otherwise, you have a pretty
non-deterministic solution set that arbitrarily picks from amoungst the
reasons to reach a particular conclusion.

This can come up with operations like union. I expect it also with
named graphs, or graphs with provenance.

> (quoting from http://www.joseki.org/client_app.html)

I think that depends on what we mena by "results". If results include
the portion of the graph that intersects the query, they it seems
like, if two parts of the graph intersect with the solution, you may
well want to report them both, even if they lead you to the save
variable bindings. Not having done the definition exercise, I'm just
trying to guess what will be easiest to define.

> So... which subgraph does Algae return when asked for a subgraph?

If you ask for a union, you get the result set above. The above output
is what you get when you ask for that serialized as one subgraph per
solution. If you specify an output mode like RDFXML, you'll get a
graph with all of those statements mushed together.

 homer:/home/eric$ ./union-alg.sh -sClass n3
@prefix : <http://example.org/n#>
A1 p2 C .
A2 p3 D .
A3 p2 C ;
   p3 D .

As opposed to the one with the shortcut or:

 homer:/home/eric$ ./shortOr-alg.sh -sClass n3
@prefix : <http://example.org/n#>
A1 p2 C .
A3 p2 C .

(The difference is the opperator):
 homer:/home/eric$ diff union-alg.sh shortOr-alg.sh 
38c38
<  ( ?n p2 C |& ?n p3 D ))
---
>  ( ?n p2 C || ?n p3 D ))

> Also...
> The example Rob gave in his message of Tue, 8 Jun 2004 07:45:54 -0700
> "find everyone who is friends with Eddie or friends with Jane"
> is more concrete. Please consider using it.

Yeah, I got lazy. Sorry.
This case has different predicates in the disjunction so it would be
like "find everyone who is friends with Eddie or neighbors with Jane."
-- 
-eric

office: +81.466.49.1170 W3C, Keio Research Institute at SFC,
                        Shonan Fujisawa Campus, Keio University,
                        5322 Endo, Fujisawa, Kanagawa 252-8520
                        JAPAN
        +1.617.258.5741 NE43-344, MIT, Cambridge, MA 02144 USA
cell:   +1.857.222.5741 (does not work in Asia)

(eric@w3.org)
Feel free to forward this message to any list for any purpose other than
email address distribution.