Re: FYI: A suggestion for an additional simplification

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 England

Received on Wednesday, 9 May 2007 13:25:23 UTC