Re: FYI: A suggestion for an additional simplification

From: Seaborne, Andy <andy.seaborne@hp.com>
Date: Wed, 09 May 2007 14:25:07 +0100
Message-ID: <4641CBB3.4030804@hp.com>

```

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

This archive was generated by hypermail 2.3.1 : Wednesday, 7 January 2015 15:00:53 UTC