Subject: Re: Can we fix BYSETPOS? (Proposed Restrictions)

From: [email-masked]
Date: Wed, 20 Jun 2001 09:58:26 -0400

[email-masked] wrote on 06/18/2001 04:05:26 PM:
> Ah -- you are right. I can't think of a way to solve it either, and it 
is
> a very practical case. Looks like I'll have to abandon my proposal for
> restrictions.

I think that not allowing BYSETPOS for recurrence sets that have fixed 
instance counts (ie: Ones that have only BYHOUR, BYMINUTE or BYSECOND 
subcomponents) can still be included for the reasons I sent last week.  It 
is not unfeasible for this and would probably make describing BYSETPOS 
easier (ie: It is only useful for sets that have variable instance counts 
hence the original requirement that at least 1 BYxxx subcomponent must be 
there too). 

However if you want to abandon the restrictions I would suggest that we 
still add some clarifying text about BYSETPOS to the revision and include 
some examples like Jonathan & I hashed over in a different thread on this 
topic.

Bruce
===========================================================================
Bruce Kahn                                INet: [email-masked]
Iris Associates                          Phone: 978.392.5335
Westford, MA, USA 01886                    FAX: and nothing but the FAX...
Standard disclaimers apply, even where prohibited by law...

---

From: Jonathan Lennox <[email-masked]>
Date: Wed, 20 Jun 2001 13:35:34 -0400 (EDT)

> hence the original requirement that at least 1 BYxxx subcomponent must be 

This restriction doesn't do anything to accomplish my goal of setting
restrictions, i.e. to ensure that processing of recurrence rules is
computationally bounded (other than "bounded by 31 million recurrences",
which isn't sufficient).

-- 
Jonathan Lennox
[email-masked]

---

From: "Shannon J. Clark" <[email-masked]>
Date: Wed, 20 Jun 2001 14:13:48 -0500

It sounds like we have discovered at least TWO issues with BYSETPOS

One - even amongst working group members, who presumably have read the specs
and thought about it a great deal there is much confusion about how to
interpert BYSETPOS and how to write RRULES to express certain conditions
(Such as repeat on "the last Tuesday of every April and June for every
year" )

Two - we have a computational bounds issue with RRULES that create large
and/or highly computationally complex sets of potential reoccurrences -
which then need to be evaluated to fit a COUNT, BYSETPOS, or UNTIL
conditional. As Jonathon has pointed out in his email - this is highly
dependant on a common understanding of the SET that rules like BYSETPOS
works on - clearly this is an area that needs clarification and explanation.

I suggest that we look at arriving at a common understanding of issue One
above, and then based on the common understanding describe the cases which
generate computationally unbound (i.e. are exponential in computational
requirements) and look for solutions to limit those cases.

My personal thought is that there may be mathematical tricks that can be
used to place bounds on many cases to reduce computational issues from
unbound to manageable (i.e. many times you can limit the expansion of an
RRULE to a set that captures the period for which you are concerned - by
doing so you place additional bounds that may help limit and resolve an
otherwise difficult calculation. Additionally, there may be structural
tricks that can work on an RRULE expression to transform it to an equivalent
form for computation - while preserving the original form for encapsulation
of intent and meaning (i.e. the difference between COUNT and UNTIL - in many
cases they can be transformed at runtime but you may want to preserve in
storage).

Furthermore there are at least THREE use cases to consider when looking at
RRULES:

A. Evaluating the question "Does this specific event occur NOW? (or within
another FIXED interval of time)? - note this COULD be a Boolean query -
unconcerned with the specific occurrence TIME or NUMBER of occurrences, just
with whether or not the event occurs during the interval in question - you
have to also look at how you define the interval - i.e. do you include the
boundaries within or outside of the interval.

B. Evaluating a SET of events to answer the question - WHICH EVENTS occur
during a given interval? - and returning an order set of those events - this
requires that in some way ALL events in the calendar are checked for whether
or not they could occur during the interval in question, and for those that
could that all occurrences are evaluated and then ordered. The one advantage
we have from a computational point of view is that this is a bound case -
with limits on the start and end of the interval in question - these in turn
can be used to eliminate a large number of potential events, and hopefully
reduce the computational time required to expand RRULES of the remaining.

C. Populating a "FULL" calendar - this is a strawman case since events are
allowed to reoccur "FOREVER" all use cases MUST have a bounds place on an
initial query AND/OR must continue to reevaluate RRULES that are "FOREVER"
as the use requires information further and further out - in point of fact
the time systems currently defined and used by iCalendar have a year 9999
issue :-)

An additional question might be of the following form - GIVEN a "new"
event - does it overlap with any existing events in the calendar? This
however may in most cases by a use for FREEBUSY information - which is in
turn generated by evaluating the events on the calendar, looking at TRANSP
settings, expanding RRULES for the required events, and building up this
information.

Hope this is helpful in focusing the discussions.

Shannon

-----Original Message-----
From: [email-masked]
[mailto:[email-masked]]On Behalf Of Jonathan Lennox
Sent: Wednesday, June 20, 2001 12:36 PM
To: [email-masked]
Cc: Eric Busboom; Graham Gilmore; [email-masked]
Subject: Re: Can we fix BYSETPOS? (Proposed Restrictions)

On Wednesday, June 20 2001, "[email-masked]" wrote to "Eric Busboom,

--
Jonathan Lennox
[email-masked]

---

From: Jonathan Lennox <[email-masked]>
Date: Wed, 20 Jun 2001 16:31:23 -0400 (EDT)

> It sounds like we have discovered at least TWO issues with BYSETPOS

I agree with your general statement.  It's a very good summary.
I have a few comments on specific points, though.

> (Such as repeat on "the last Tuesday of every April and June for every

I think there probably isn't too much disagreement about the "natural" way
to represent most common rules.  The disagreements we're having (I think)
are about how to interpret rules which are perhaps "un-natural" ways of
representing certain recurrences.

> works on - clearly this is an area that needs clarification and explanation.

Yes.  The smaller the set, clearly, the less computation needed.

> requirements) and look for solutions to limit those cases.

Just to clarify this a bit -- "exponential" is a bit strong here.   No
algorithms I've found are worse than linear, in the *values* of the
parameters.

The problem, though, is that these values can be arbitrarily large.
Especially, DTSTART can be located in the absurdly distant past, DURATION
can be arbitrarily long, and BYSETPOS values are (apparently) limited only
by "seconds per year".

> cases they can be transformed at runtime but you may want to preserve in

Yes.  The problem is that "many cases" aren't "all cases", at least I think
they aren't.  The limited-expansions and the structural tricks work nicely
for resolving the problems with DTSTART and COUNT.  However, I haven't yet
found any similar tricks for DURATION and BYSETPOS, and I'm not sure any
such tricks are possible.

> boundaries within or outside of the interval.

Note also that DURATION is very relevant for this.  Usually, the question
you want to ask is "Is this specific event occuring now" or "is this event
occuring within this interval of time", not "does this event start now /
within this interval".

A number of existing calendaring systems get this wrong -- if you ask them
to show "events on Tuesday", they won't show a four-hour event which begins
at 10PM Monday.

This is why I restricted the acceptable values for DURATION in my initial
RECUR subset for CPL.  CPL only cares about your "is this event occuring
now" case, but this is equivalent to "does this event start between DURATION
ago, and now."

> Hope this is helpful in focusing the discussions.

I hope so too...

-- 
Jonathan Lennox
[email-masked]