Re: RECAP & Questions of CPL RECUR Issues.

[Jonathan Lennox <lennox@xxxxxxxxxxxxxxx>]

On Monday, May 14 2001, "Eric Busboom" wrote to "<ietf-calendar@xxxxxxx>, <francis@xxxxxxxx>, <lennox@xxxxxxxxxxxxxxx>" saying:

> John, Johnathan,
> 
> This is how I understand the problems that the IPTEL group identified with
> RECUR. Are these correct?
> 
> 	(1) Telephony equipment must be able to check that a given time is
> 	included with in the events specified by a DTSTART, DURATION and set of
> 	RRULES, RDATEs, EXRULEs and EXDATEs in constant time. ( Or is it
> 	O(n) for the number of elements in the byrules? ) Generally, RECUR
> 	rules require O(n) in the number of occurrences.

O(n) in the textual length of a rule, specifically.  (With the constant
factor small, hopefully.)  This is clearly inevitable, because the server
has to read and parse the rule in order to execute it.

O(1) in the value of any parameter, though.

> Other problems that have been identified include:
> 
> 	(2) Because the RRULEs are so complex, and because there are many
> 	different ways to specify a single set of occurrences, it will be very
> 	difficult for a CUA to create a GUI that can manipulate any arbitrary
> 	incoming RRULEs.

This is the issue John identified.  Seeing what existing GUIs do was a
motivating factor for my decisions as to which parts would be okay to drop,
but it's not directly behind my decision to create a subset.

> The proposed solutions are:
> 
> 	(1) Remove COUNT
> 	(2) Remove BYSETPOS
> 	(3) Remove byrules and frequencies for hour, minute and second.
> 	(4) Limit the duration of an event to less than 24 hours.

> (1) and (2) are proposed to directly allow constant time operation. (3)
> and (4) are proposed to disallow a RRULE from generating any two
> occurrences that overlap. Overlapping rules compicate a specific algotithm
> for performing (1).

It's a bit more complicated than "occurences which overlap", but yes, that's
basically correct.

> Now, for some questions.
> 
> For (1). Is it O(1) or O(n) with number of BYrule elements? The body of
> draft-stracke-calsch-rrule-subset-XX.txt says O(1), but the algorithm in
> the appendix implies O(n). Or does the O(1) mean "O(1) in number of
> occurrences?"

See above.  O(n) in the textual size of the rule; O(1) both in the number
occurences and in the elapsed time since DTSTART.  (I suspect any algorithm
which can resolve COUNT and BYSETPOS has to be non-constant-time in at least
one of these.)

> Past discussions noted that the algorithm may be O(1) in a single rule,
> but will be linear with respect to multiple rules. So what would you do
> with a client that always expanded recurrence rules to RDATE?  (thereby
> forcing O(n). ) Would the telephony equipment set a limit on the maximum
> number of RDATE, RRULE, EXRULE and EXDATE properties it would accept, and
> reject anything over that limit?

If it always expanded its rules, then yes, it would.  I suppose the
equipment would have to have a "don't be absurd" response if someone dropped
a 10-megabyte rule on it.

> And, if the algorithm is O(n) with number of rules, and actually O(n) with
> number of BYxxx rule part elements in each rule, then in the general case
> the algorithm is O(n^2) in the size of the RRULE, a long way from O(1).

No, because rules are resolved sequentially, from what I understand.  Check
the first one, check the second one, etc.  Yes, it's O(m*s) (if you have 'm'
rules, each of average size 's'), but that's the same thing as O(n).

> So, do you really need O(1), or can you get by with an very fast check of
> the upper bound of the occurrence set? That is, what if you could quickly
> determine if the rrule is too complex for your processor to handle?
> 
> Also, please review the current proposed text change for for RECUR, issue
> #15 at:
> 
> 	http://softwarestudio.org/iCal/ProposedChanges.txt
> 
> These restrictions prevent many absurd examples like the one in
> draft-stracke-calsch-rrule-subset-XX.txt.

Yes, but I think they're orthogonal.  (I.e. they add additional restrictions
to prevent paradoxical rules, but don't alter theoretical algorithmic
complexity needed needed to resolve an RRULE.)

-- 
Jonathan Lennox
lennox@xxxxxxxxxxxxxxx