Re: Proposal to drop disjunction requirement

On Fri, Oct 01, 2004 at 04:15:11PM -0500, Dan Connolly wrote:
> On Fri, 2004-10-01 at 13:21, Steve Harris wrote:
> > On Fri, Oct 01, 2004 at 01:22:24 -0400, Kendall Clark wrote:
> > > 
> > > On Fri, Oct 01, 2004 at 06:17:16PM +0100, Steve Harris wrote:
> > > 
> > > > conjunctive ones, but it explodes the number of queries needed
> > > > dramatically.
> > > 
> > > In cases where the implementation strategy is based on RDBMS/SQL or in
> > > every case? I genuinely don't know.
> > 
> > In every case - the algorithm prduces a number of prurely conjunctive
> > expressions from a mixed dis/con-juntive one.
> 
> Really? I can't think of an algorithm for the simplest case:
> 
>  (<book1> dc:title "War and Peace") OR (<book2> tc:title "Moby Dick")

I've played around a lot with this and haven't come up with a graph
that I can't express in SQL. SqlDB expresses that on on an triples
store as:

... FROM __Holds__ AS s1
   WHERE s1.p='<dc.title>'
     AND ((s1.s='<book1>'
           AND s1.o='War and Peace')
          OR (s1.s='<book2>
              AND s1.o="Moby Dick"))
and on a normalized store as (making up a reasonable db schema here):

... FROM Books AS Books_1
   WHERE ((Books_1.s='<book1>'
           AND Books_1.o='War and Peace')
          OR (Books_1.s='<book2>
              AND Books_1.o="Moby Dick"))

A harder case is when you have different relations in the different
side of the disjunction. This is handled at SQL query compliation time
(after you've built your constraints tree).
  for each branch of the disjunction
    for each table that's not in the other branches
      change the JOIN to an OUTER JOIN
      apply all earlier constraints for this branch to this JOIN
      replace the option with the single constraint that it not be NULL
e.g.
  (?x foaf:name "Bob Smith) OR (?x foaf:given "Bob . ?x foaf:family "Smith)
==> 
... FROM __Holds__ AS s1
    LEFT OUTER JOIN __Holds__ AS s2 ON s1.subject=s2.subject
                                   AND s1.p='foaf:given'
                                   AND s2.p='foaf:family'
   WHERE (s1.p='foaf:name'
          OR s2.id IS NOT NULL)

The earlier queries are just a degenerate form of this.


I'm pretty motivated by the notion that people don't think this
way. I'd like to leave disjunction in and let the machine figure this
stuff out for me. In fact, is there a program I can use to write mail
like this?

> Oh.. you mean you turn it into *multiple* queries. Maybe I see.
> 
> Don't you need negation in some cases?
> 
> [...]
> > > I can't imagine
> > > ordinary folks writing them.
> > 
> > Bear in mind that those are the /exact/ translations, the optional
> > expression users really write are the natural ones and dont have the hairy
> > disjuntive value constraints.
> 
> That seems to be the most relevant point/question, to me: do we
> expect users to find the optional constructs straightforward for 80%
> to 95% of the cases? Or do we expect them to say "hey; where's the OR
> thingy?" in their first week of usage?
> 
> -- 
> Dan Connolly, W3C http://www.w3.org/People/Connolly/
> D3C2 887B 0F92 6005 C541  0875 0F91 96DE 6E52 C29E



-- 
-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.