Subject: Re: Current thinking on CPL/iCalendar

From: [email-masked]
Date: Tue, 20 Mar 2001 10:31:33 -0500

Patrik replied:
> Question: Is not the requirement for O(1) that the interval between
> events have to be longer than the length of the event itself?
>
> I.e. removing support for sub-24h recurrances seems too arbitrary if
> not really needed.

It may be part of the IPTEL but its not part of CALSCH's requirements.  I
dont see any rationale for this need so Im not sure _why_ it would exist.

> >Our training dept schedules multiple instances of the "same" class
> >which sometimes overlap.  I could easily be swayed by the argument
> >that there should be multiple "threads" on a per instructor basis, or
> >perhaps by room.  Just pointing out one possibility.
>
> The need for non-overlapping events is the largest requirement for
> O(1) isn't it?

Perhaps Im just not focused enough on O(1) but I do not see how restricting
to non-overlapping entries makes the performace faster.  I can understand
restricting the use or values in, say, an RRULEs due to potentially heavy
roll times.  I dont see how overlapping, explicit RDATEs violates or
prohibits O(1) so can someone please codify why?

Similar example to Daves:
A theatre lists a movie once but it may have overlapping show times.  It is
not that logical to have them PUBLISH movie times based on each individual
thatre; its more logical to just list all the showing times for a title.
A museum or company that conducts tours may have staggered schedules.
Instead of scheduling on a tour guide by tour guide basis, they are
scheduling on a tour by tour schedule.

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...
[email-masked] wrote on 03/20/2001 09:30:32 AM:

> At 08.01 -0500 01-03-20, David Madeo wrote:
> >John Stracke wrote:
> >
> >>  We talked about the CPL/iCalendar issue at the calsch dinner
> >>  tonight.  The outcome (such as it is):
> >>
> >>      + The interval between instances must be less than
> >>          24 hours.
> >
> >I'm assuming this is reversed and should be "more".  Otherwise my
> >weekly meetings are going to be a bit difficult.
> >A counter example would be the pill that I have to take every four
> >hours.
>
>
> >  >    * Possible impact on existing (or potential) applications:
> >>          o No overlapping instances--can anybody provide a
> >>            plausible scenario where you'd want them?
> >
> >Our training dept schedules multiple instances of the "same" class
> >which sometimes overlap.  I could easily be swayed by the argument
> >that there should be multiple "threads" on a per instructor basis, or
> >perhaps by room.  Just pointing out one possibility.
>
> The need for non-overlapping events is the largest requirement for
> O(1) isn't it?
>
> Because of this I think it should be stated as the main goal for
> these changes.
>
>     paf
>
>
> --
> Patrik Fältström <[email-masked]>       Internet Engineering Task Force
> Area Director, Applications Area                   http://www.ietf.org
> Phone: (Stockholm) +46-8-6859131            (San Jose) +1-408-525-8509
>         PGP: 2DFC AAF6 16F0 F276 7843  2DC1 BC79 51D9 7D25 B8DC

---

From: Steve Mansour <[email-masked]>
Date: Tue, 20 Mar 2001 08:04:19 -0800

[email-masked] wrote:

> A theatre lists a movie once but it may have overlapping show times.

but they will be in different locations.

> It is

I don't know. It doesn't seems more logical to me if I was generating PUBLISH
events.  How would you list the LOCATIONs ?

> scheduling on a tour by tour schedule.

So in other words, the tour is 2 hours, there's two of them every day, they
start at 10:00 and 10:30 ?

This could be done with two separate recurring meetings as well.  May not be as
elegant, but then I can't envision the UI that would allow you to create such
meetings as a single event.

Seems like there is a reasonable workaround for the overlapping recurrences.  A
clarification stating that recurrence intervals must be greater than the
duration of the event seems like it does a lot more good than harm.

-Steve

---

From: Alan Davies <[email-masked]>
Date: Tue, 20 Mar 2001 11:57:35 -0600

I've been having a think about alternative ways of solving the problem,
and it seems that there should be a way to find if a time matches
a given rule in constant time without any restrictions on the duration
or recurrence interval (I haven't looked into COUNT or BYSETPOS-
it seems too obvious that you're right on those).

The algorithm that you proposed in the CPL draft relied on certain
restrictions to ensure that it could complete in constant time.

We had a look at trying to apply some simple set theory to the problem, and it
seemed that it should be solvable, so I bashed out some simple
formulas, which are given below.

In an RRULE, there are a bunch of parameters that are easy to check for-
BYWEEKNO, BYYEARDAY, etc.- we can ignore those as they're not causing
any problems.

The question comes with the FREQ, INTERVAL, and DURATION.
However, if this were written as an equation or inequality,
these would all be constants, only the instance number would vary.

It seems that the problem we're trying to solve then is this:

Does an integer value of n exist such that both
k * n  >= target date    and     k * n + d < target date
are true? (k is a constant representing the interval and frequency, start date
has been factored out, d is a constant representing duration)

Dividing target by k and flooring to the nearest whole number gives us a 
candidate
value of n. This can be then run through the above inequalities. If this 
candidate matches,
then an earlier value of n MAY also match (i.e. if d is greater than k), 
but if this candidate
doesn't match, then no value of n will.

Is this a gross oversimplification?

--Alan

---

From: Jonathan Lennox <[email-masked]>
Date: Tue, 20 Mar 2001 13:11:24 -0500 (EST)

> prohibits O(1) so can someone please codify why?

They don't.  The prohibition is on overlapping recurrences within an RRULE,
not on overlapping recurrences within an entire RECUR.

(For IPTel folks: this means "the prohibition is on overlapping recurrences
within a <time>, not on all the <time> nodes within a <time-switch>.)

The *total* resolution time is O(n) in the number of sub-rules of the
RECUR / outputs of the <time-switch> node, but since this is proportional to
the length of the iCalendar object / CPL, that's inevitable anyway.

-- 
Jonathan Lennox
[email-masked]

---

From: Jonathan Lennox <[email-masked]>
Date: Tue, 20 Mar 2001 13:58:48 -0500 (EST)

> it seems too obvious that you're right on those).

If this is possible, it'd be wonderful.  This was certainly always my ideal
solution.

> We had a look at trying to apply some simple set theory to the problem,
> and it seemed that it should be solvable, so I bashed out some simple

Be careful with this.  You need to distinguish between "expanding" and
"contracting" BY* parameters.  Thus, for instance, in
RRULE:FREQ=MONTHLY;BYWEEKDAY=TU,TH, the BYWEEKDAY parameter causes the
recurrence to happen *more* often than it otherwise would.

In my algorithm in the CPL spec, I call the smallest of the FREQ interval
and the BY* intervals the "Minimum Unit".  I'm not sure that's the clearest
name for this -- I've never been good at coming up with names for
things. :-)

> these would all be constants, only the instance number would vary.

Yes.  (Assuming you use the minimum unit rather than the raw FREQ.)

> has been factored out, d is a constant representing duration)

Yes.  (Modulo some trickiness that DTEND and DURATION don't actually specify
the same thing, if a DST transition is present.)

Notice that 'k' isn't actually a constant if you have FREQ=MONTHLY or
FREQ=YEARLY.  (In fact, it's technically not a constant for all units
greater than HOURLY if you take DST transitions into account, but you can
just do your math based on a count of days.)

Also note that you may not actually have to calculate 'n', depending on how
you're dealing with INTERVAL.  You just have to calculate (dtstart + k * n).
This is what I call the "Candidate Start Time" in my algorithm.

Because INTERVAL modifies the FREQ, not the Minimum Unit, my algorithm just
lets 'k' be the minimum unit, in the calculation you describe above.

INTERVAL is checked in a separate calculation -- I check that
'floor((candstart - dtstart) / FREQ)' is a multiple of INTERVAL.  There may
be different ways of approaching this, though.

> candidate value of n. This can be then run through the above
> inequalities. If this candidate matches, then an earlier value of n MAY
> also match (i.e. if d is greater than k), but if this candidate doesn't
> match, then no value of n will.  Is this a gross oversimplification?

No, unfortunately.  The problem is that your first candidate value of 'n'
may fail to match the BY* restrictions, but subsequent candidates would.

Consider 
DTSTART:19970902T090000Z
DURATION:P2D
RRULE:FREQ=DAILY;BYDAY=TU

I.e., this is a recurrence which occurs every week, starting at 9 AM
Tuesday, and lasts for two days -- i.e. until 9AM Thursday.  Note that this
is *not* a self-overlapping recurrence, but its duration is longer than its
minimum unit.

Let's say we want to check if the date "Wed, Mar 21 13:42:55 GMT 2001" falls
within this recurrence.

We quickly determine that 'k' is one day.

We calculate the candidate start time, and find that "Wed, Mar 21 09:00:00
GMT 2001" is the latest possible candidate start time (the latest 
dtstart + k * n).

We then verify the other parameters, but find that the the BYDAY rule is
violated, so that this candidate start time is *not* a valid start time.  By
the rule you expressed above, we would reject the time.

However, this date *is* of course within the recurrence -- we just need to
use the earlier (valid) candidate start time "Tue, Mar 20, 09:00:00 GMT
2001".

Do you see any more efficient way to determine this?  Given that if we
allow the above rule, we really don't have anything cleanly separating us
from absurdities like "When the 182nd day of the year falls on a Thursday,
schedule something for the eighty weeks that follow":

DTSTART:19970902T000000Z
DURATION:P80W
RRULE:FREQ=YEARLY;BYYEARDAY=182;BYDAY=TH

which will require 560 checks of the BYDAY and BYYEARDAY parameters against
candidate start times, under my algorithm.

If you can come up with an O(1) algorithm for this, I'd be wonderfully
grateful.  I think it'd resolve all the current points of controversy.

-- 
Jonathan Lennox
[email-masked]

---

From: John Stracke <[email-masked]>
Date: Tue, 20 Mar 2001 14:04:51 -0600

[email-masked] wrote:

> It may be part of the IPTEL but its not part of CALSCH's requirements.

I think we have two reasons calsch needs to do something along these lines.
The first is that we would benefit no less than CPL from an O(1) evaluation of
recurring events.  Even if you expand your recurring events and put all the
instances into the database, it'd be nice to reduce the cost of that
expansion.  Also, at the moment, expanding the instances like that is pretty
much the only feasible strategy; expanding on the fly is impractical.  O(1)
evaluation would open up the field of design alternatives, which would let
people pick the right strategy for their scenario.

However, we may be able to achieve O(1) without banning the sub-day
recurrences.  If so, then we still have the issue of usability; the current
RECUR grammar is extremely complex, far too complex to express in a simple
UI.  This means that we'll get implementations that support only subsets
(there will also be those that use complex UIs, but they'll lose out to the
simple UIs over time); if we don't want to wind up with *different* subsets,
non-interoperable ones, then we'd better pick a single subset *now*.

--
/==============================================================\
|John Stracke    | http://www.ecal.com |My opinions are my own.|
|Chief Scientist |=============================================|
|eCal Corp.      |That is correct. I'm out of fuel. My landing |
[email-masked]|gear is jammed. And there's an unhappy bald  |
|                |eagle loose in the cockpit.                  |
\==============================================================/

---

From: John Stracke <[email-masked]>
Date: Tue, 20 Mar 2001 13:58:30 -0600

> but they will be in different locations.

...on the other hand, the users don't care about those different locations.

---

From: Alan Davies <[email-masked]>
Date: Wed, 21 Mar 2001 15:34:33 -0600

Thanks for the clarification. There are a few subtleties to the way that
the BY* rules interact with each other and with FREQ, particularly
when they can both "expand" or "contract" the search space.

 > candidate start times, under my algorithm.

This example wouldn't be allowed according to Eric's proposed text at
http://www.imc.org/ietf-calendar/mail-archive/msg05424.html

         [a] If the BYYEARDAY part appears in a rule , no other date rule
         part may appear. (2)

Although I do get the point, and I'm sure it's not difficult to come up
with even more absurd examples that would still be allowed.

Incidentally, Appendix A of the CPL Draft
http://search.ietf.org/internet-drafts/draft-ietf-iptel-cpl-04.txt
you write:

         8.   For every byxxx rule, confirm that the candidate start time
              matches one of the options specified by that byxxx rule. If
              not, fail NOMATCH.

Does your definition of constant time take into account situations such
where although only one time is being compared, an unusually high number
of comparisons may have to be made?:

DTSTART:20011231T000000Z
DURATION:P1D
RRULE:FREQ=YEARLY;BYYEARDAY=1,2,3,4,5,6, [...] ,365

or even

RRULE:FREQ=YEARLY;BYYEARDAY=1,2,3,1,2,3, [...]

etc.

These are somewhat absurd (especially the second one, which
should be considered invalid even though I don't think it's explicitly
stated in the recurrence rule section of 2445)

--Alan

---

From: "Shannon J. Clark" <[email-masked]>
Date: Wed, 21 Mar 2001 16:26:48 -0600

Reading over this - and also reading the threads about timezones and DST, I
had the following thoughts for example situations. If the rrules and the
standard in general can handle these I think it would be good.

Take a case of someone putting in a reoccurring work schedule (for example
an airline pilot).

The schedule might be something like: On for 16 hours - off for 32hrs -
repeat. The issue becomes how to calculate during DST changeovers (when a
there is a day with 23 hrs, and a day with 25hrs). In this case the few
occurrence of being off for 31 hrs or for 33 hrs are probably not a big
deal, BUT if the numbers were closer you might hit up against regulatory
restrictions on # of hours in a 7 day period (or for a case of Truckers who
have mandatory periods of rest you might have a similar issue - on the DST
day changeovers their scheduling software should be "smart" enough to know
that 12:00-8:00AM is not equal to 8 hours of sleep that day.

This also raises the counterintuitive thought that One Day is != 24hrs in
all cases - something probably too obscure and complex for most user
interfaces.

(We'll leave aside the issue of Leap Seconds for the moment - something only
important for really precise computer systems)

Anyway just another wrinkle to suggest.

Shannon

-----Original Message-----
From: [email-masked]
[mailto:[email-masked]]On Behalf Of Alan Davies
Sent: Wednesday, March 21, 2001 3:35 PM
To: [email-masked]
Cc: [email-masked]
Subject: Re: Current thinking on CPL/iCalendar

DTSTART:20011231T000000Z
DURATION:P1D

or even

etc.

--Alan

---

From: Alan Davies <[email-masked]>
Date: Wed, 21 Mar 2001 16:57:43 -0600

If the current "bounded time resolvable" subset of RRULEs is adopted, this
example wouldn't be allowed, as it uses a sub-day recurrence.

If it was allowed, a good implementation should be able to cope with this,
perhaps by converting local times to and from UTC before performing
arithmetic on them in these cases. It's not stated explicitly in RFC2445 
though.

And you're right- strangely RRULE:FREQ=HOURLY;INTERVAL=24
can produce different results to RRULE:FREQ=DAILY

--Alan

---

From: Jonathan Lennox <[email-masked]>
Date: Wed, 21 Mar 2001 17:59:03 -0500 (EST)

> when they can both "expand" or "contract" the search space.

Yes.  (Though the degree to which you have to worry about "expand" /
"contract" behavior depends on your algorithm, somewhat.)

> with even more absurd examples that would still be allowed.

The BYYEARDAY part isn't essential.  It's almost the exact same recurrence
(except for leapyear wiggles) if you specify the starting date with BYMONTH
and BYMONTHDAY instead. 

In general, it's not clear to me whether Eric's restrictions from that
message are actually terribly useful.  It looks like the intention was to
prohibit self-contradictory RRULEs.  While I understand the desire to do
this, I don't think it's in general possible.

For example, consider
DTSTART:19970902T000000Z
RRULE:FREQ=MONTHLY;INTERVAL=6;BYMONTH=6,12

"Every six months from September 2nd 1997, when this falls in June or
December."  There will -- clearly -- never be such an occurence, but Eric's
restrictions, or most other restrictions I can think of, would still allow
this construct.

That said, I don't think self-contradictory RRULEs are a problem.  Though
they're not actually useful, their interpretation is clear -- they specify a
single occurence, their DTSTART.  In the interest of making the spec simple,
I think it's better to allow them, note that they're possible, and probably
clarify that a COUNT parameter (if we keep them) for a self-contradictory
RRULE should be ignored.

> stated in the recurrence rule section of 2445)

Yes, the statement of the running time as "O(1)" is a bit oversimplified.
What I should have said -- and what I think is inevitable -- is that the
running time is linear in the textual length of the RRULE, and independent
of the size of any of its values.

-- 
Jonathan Lennox
[email-masked]