From: Seaborne, Andy <andy.seaborne@hp.com>

Date: Wed, 09 May 2007 14:25:07 +0100

Message-ID: <4641CBB3.4030804@hp.com>

To: ogbujic@ccf.org

CC: public-rdf-dawg@w3.org

Date: Wed, 09 May 2007 14:25:07 +0100

Message-ID: <4641CBB3.4030804@hp.com>

To: ogbujic@ccf.org

CC: public-rdf-dawg@w3.org

Chimezie Ogbuji wrote: > I recently began an attempt to implement the mechanics of "12.2.1 > Converting Graph Patterns" as a reduce function (a functional > programming idiom [1]) and came across an additional simplification that > might be useful to list in Step 5: Simplification > > OPTIONAL graph patterns juxtaposed against an empty pattern can be > reduced to just the graph pattern: > > Replace LeftJoin({},A,expr) with Filter(expr,A) I think the notation is confusing the issue here and the notation needs some editorial fixing. {} isn't the empty set - it's the empty graph pattern (actually, there are two empty patterns, a BGP with no triple patterns, and a group with nbo elements. Both should give the same answers - both need to be explicitly defined). The empty pattern is no restrictions on the variables in a soltuion and it is the join identity. As an empty group, the solution to the pattern is one row or no bindings. But soon after, in sec 12, "{" "}" start to be used as the set part of a multiset which is set notation. Confusingly, one row of no bindings is the multiset: ## Set notation { {} } : that is a set of the empty set Card({}) = 1 Now, looking LeftJoin (the condition is not a factor here): LeftJoin({},A) Suppose A is some pattern that never matches the data. So A matches with the empty multiset. LeftJoin(X, nothing) is X Write N for the empty multiset. Join(N, X) = Join(A, X) = X for all algebra expressions X Joining with a table of no rows is a table of no rows. Diff(X, N) is X. In LeftJoin({},A), X is {} so LeftJoin({},A) is the solutions to {} as a pattern. I pulled out the Join() simplification because it makes the examples clearer. You can get a lot of empty pattern in the translation which add nothing. It's not the intention to enumerate all possible simplifications (but the most interesting ones are dependent on the patterns anyway). Thanks for finding this confusion of notation, (if only there were more kinds of parentesises in the world!). Andy > > ---------- > > This seems to follow from: > > LeftJoin(Omega1, Omega2, expr) = Filter(expr, Join(Omega1, Omega2)) > set-union Diff(Omega1, Omega2, expr) > > Omega1 -> [] - an empty multiset of solution mappings (an empty graph > pattern will not have any solutions) > > Filter(expr, Join([], Omega2)) set-union Diff([], Omega2, expr) > > Join({}, A) -> A > > Filter(expr, Omega2) set-union Diff([], Omega2, expr) > > Diff([],.. any solution mapping multiset ..,expr) => [] (by definition) > > Filter(expr, Omega2) set-union [] > > Filter(expr, Omega2) > > [1] http://en.wikipedia.org/wiki/Fold_%28higher-order_function%29 > -- Hewlett-Packard Limited Registered Office: Cain Road, Bracknell, Berks RG12 1HN Registered No: 690597 EnglandReceived on Wednesday, 9 May 2007 13:25:23 GMT

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