W3C home > Mailing lists > Public > public-prov-wg@w3.org > March 2012

Re: closing old collection issues -> the question of monotonicity of provenance

From: Paolo Missier <Paolo.Missier@ncl.ac.uk>
Date: Thu, 29 Mar 2012 12:15:59 +0100
Message-ID: <4F74446F.5010607@ncl.ac.uk>
To: Stian Soiland-Reyes <soiland-reyes@cs.manchester.ac.uk>
CC: Paolo Missier <paolo.missier@newcastle.ac.uk>, "public-prov-wg@w3.org" <public-prov-wg@w3.org>
Stian

ok thanks

the functionality requirement is actually still on the table.
That's also the reason the constraint section is empty (the text is actually in a temp doc in working-copy).

The example you gave on the empty collection with an assertion on membership brought it up again:
>>> entity(c2, [prov:type="EmptyCollection"])
>>> derivedByRemovalFrom(c2, c1, {"k1",v1})
>> the two statements above can't go together:  c2 is either empty, or is
>> derived from c1 by removal. You can't have both...
> Those are perfectly valid statements (except for {}() syntax), it
> simply means that c1 had only a single member, and thus c2 is empty,
> not having {("k1", v1)}.
I commented on this earlier. To me it boils down to whether or not it matters that the provenance statements that collectively 
describe the state of a collection are monotonic or not.
We have not encountered this before because all other relations are monotonic, as there is no negation in the language (i.e., you 
can't say derivedFrom(a,b) today, and then "not derivedFrom(a,b)" tomorrow).

But a statement that says that an element is removed from a collection breaks monotonicity:

yesterday my provenance included:

  derivedByInsertionFrom(c1, c,  {("k1", e1), ("k2", e2)})
  derivedByInsertionFrom(c1, c,  {("k3", e3)})

so yesterday I believed that c1 = { ("k1", e1), ("k2", e2), ("k3", e3)}

today I have new statements:

  derivedByRemovalFrom(c1, c,  { "k1"})
  derivedByInsertionFrom(c1, c,  {("k4", e4)})

so today I believe that c1 = { ("k2", e2), ("k3", e3), ("k4", e4)}

the question is: is this a problem at all?  if it isn't, then the functionality constraint can be dropped entirely. If it is, then 
its easiest to enforce it for all relation rather than just for removal.

Any thoughts?

--Paolo


On 3/29/12 11:20 AM, Stian Soiland-Reyes wrote:
> On Wed, Mar 28, 2012 at 14:52, Paolo Missier<Paolo.Missier@ncl.ac.uk>  wrote:
>> I am proposing to close very old issues that had been left pending (my
>> fault) and that come from you. It seems to me they have all been superseded
>> by recent versions, incl. today's.
> They are old, but some of them are still not addressed.
>
>
>> http://www.w3.org/2011/prov/track/issues/135
> "Collection relations have confusing names"
>
> Closed.
>
>
>> http://www.w3.org/2011/prov/track/issues/136
> "Collection not stated as functional"
>
> The description on
> http://dvcs.w3.org/hg/prov/raw-file/tip/model/prov-dm.html#component5
> still does not say that these are functional, but that is the
> intention you are giving in these email - ie.
>
> I can't do:
>
>   derivedByInsertionFrom(c1, c,  {("k1", e1), ("k2", e2)})
>   derivedByInsertionFrom(c1, c,  {("k3", e3), ("k4", e4)})
>
> or
>
>   derivedByInsertionFrom(c1, c,  {("k1", e1), ("k2", e2)})
>   derivedByInsertionFrom(c1, c2,  {("k1", e1), ("k2", e2)})
>
> or
>
>    derivedByRemovalFrom(c3, c2, {k1, k3})
>    derivedByRemovalFrom(c3, c2, {k2, k4})
>
> or
>
>   derivedByInsertionFrom(c1, c,  {("k1", e1), ("k2", e2)})
>   derivedByRemovalFrom(c1, c, {k1, k3})
>
> etc.
>
>
> This constraint should as a minimum be listed in the now empty section at:
> http://dvcs.w3.org/hg/prov/raw-file/tip/model/prov-dm-constraints.html#term-Collection
>
> It should probably also show the inferred wasDerivedFrom statement(s).
>
>
>> http://www.w3.org/2011/prov/track/issues/137
> "Collection assertions does not guarantee isolation"
>
> This will be covered by the  last bullet point:
>
>> The representation of a collection through these relations makes no assumption regarding the underlying data structure used to store and manage collections. In particular, no assumptions are needed regarding the mutability of a data structure that is subject to updates. Entities, however, are immutable and this applies to those entities that represent collections. This is reflected in the constraints listed in Part II.
> .. given that those constraints are listed in Part II.
>
> I'll leave it open until that is the case.
>
>
>> http://www.w3.org/2011/prov/track/issues/138
> "Collection does not describe multiple additions/replacements"
>
> Closed.
>
>


-- 
-----------  ~oo~  --------------
Paolo Missier - Paolo.Missier@newcastle.ac.uk, pmissier@acm.org
School of Computing Science, Newcastle University,  UK
http://www.cs.ncl.ac.uk/people/Paolo.Missier
Received on Thursday, 29 March 2012 11:16:29 GMT

This archive was generated by hypermail 2.2.0+W3C-0.50 : Thursday, 26 April 2012 13:06:59 GMT