```Copyright ©2008  T. H. Merrett

COMP 617	Information Systems		Winter 2008		Week 7

Series Queries

1. Two motivating queries from [DiaoImmGyll:SASE+]

Query 2 captures a one-hour period in which the price of a particular stock
increased from 10 to 20 and the trading volume of the stock stayed relatively
stable.

Query 3 captures a more complex trend for each stock: in the last hour, the
volume started high, but after a period when the price increased or remained
relatively stable, the volume plummeted.

To approach these queries, we need some preliminaries.

2. Running automata.

Here's the autmaton from [week1p1].

aababb		Str(sq ch)	DFA( sS ch eS )	term( eS)
1  a	      1  a 125	     136
(a|b)*(abb|aa*b)     2  a	      1  b   1	      14
3  b	    125  a 125
4  a	    125  b 136
5  b	    136  a 125
6  b	    136  b  14
14  a 125
14  b   1

Here's a programmer-written funop [week2p1].

comp makeAutom(DFA, term, start, runauto) is
{ state automSt intg;
comp runauto(value,accum) is funop
{ automSt <- DFA[automSt,value];
accum <- [] in term[automSt]
}
automSt <- start
}

(Note		automSt <- DFA[automSt,value];
is syntactic shorthand for
automSt <-  [pick eS] in DFA[automSt,value];
The type system can probably convert from singleton unary to integer.
NB [pick eS] is also shorthand for the less direct [red max of eS].)

Let's run this on Str.
makeAutom(in DFA, in term, in 1, out runauto);
let res be fun runauto of ch order sq;
let match be red max of res;	<< NB false < true   OR  red or >>
let matchlast be red max of (sq = red max of sq) and res;

Str(sq ch) res match matchlast
1  a   f    t       t
2  a   f    t       t
3  b   t    t       t
4  a   f    t       t
5  b   t    t       t
6  b   t    t       t

3. Automata on predicates. Let's look at a STOCK relation and derive some
predicates related to queries 2 and 3 above.
let firstime be red min of time;
let firstvol be red max of if time = firstime then volume else -1;
let volstable be 0.9*firstvol <= volume <= 1.1*firstvol;
let prevprice be if time = firstime then price - 1 else
fun pred of price order time;
let priceincr be price >= prevprice;

STOCK
(symbol time price volume) volstable priceincr allVSorPI
GOOG  1000   10   1100        t         t         t
GOOG  1006   12   1400        f         t         t
GOOG  1012   10   1200        t         f         t

If we want to know whether the volume was stable or the price increased in
the period covered by this relation, we can find
let allVSorPI be red and of (volstable or priceincr)
which is true.

But if we want to detect a pattern such as tft or ttf, we need automata.

autTFT		termTFT			autTTF		termTTF
(sS pr eS)	(S)			(sS pr eS)	(S)
0  t  1	 3			  0  t  1	 3
0  f  0				  0  f  0
1  t  1				  1  t  2
1  f  2				  1  f  0
2  t  3				  2  t  2
2  f  2				  2  f  3
3  t  3				  3  t  3
3  f  3				  3  f  3

makeAutom(in autTFT, in termTFT, in 0, out runauto);
let vsTFT be fun runauto of volstable order time;
let allvsTFT be red max of vsTFT;
makeAutom(in autTTF, in termTTF, in 0, out runauto);
let piTTF be fun runauto of priceincr order time;
let allpiTTF be red max of piTTF;

And if we want to detect the combined pattern, we could combine the automata:
the two predicates combine to form the integers 0,..,3.

let automIN be 2*(if volstable then 1 else 0) +
(if priceincr then 1 else 0);

autCombined			termCombined
(sS pr eS)	(sS pr eS)	(S)
0  0  0	  2  0  0	 3
0  1  0	  2  1  0
0  2  0	  2  2  3
0  3  1	  2  3  1
1  0  0	  3  0  3
1  1  2	  3  1  3
1  2  0	  3  2  3
1  3  1	  3  3  3

makeAutom(in autCombined, in termCombined, in 0, out runauto);
let combined be fun runauto of automIN order time;
let allCombined be red max of (time = red max of time) and combined;

Of course, this is redundant for this example, because  allCombined  should
be identical to  allvsTFT and allpiTTF . But if we had more than three tuples
in STOCK, then  allvsTFT  would be true if tft occurred _anywhere_ under
volstable, and  allpiTTF   would be true if ttf occurred _anywhere_ under
priceincr ,  and we would need to write a combined automaton for the
synchronized occurrence of the patterns.

We'll need an automaton for Query 3.

4. Windowing.

Let's do some preparation for queries 2 and 3, first considering the whole of
relation STOCKS. (The stocks are GOOGle and, later, BALLard.)
let firstime be red min of time;
let firstvol be red max of if time = firstime then volume else -1;
let volstable be 0.9*firstvol <= volume <= 1.1*firstvol;
let firstprice be red max of if time = firstime then price else -1;
let pristable be 0.9*firstprice <= price <= 1.1*firstprice;
let prevprice be if time = firstime then price - 1 else
fun pred of price order time;
let priceincr be price >= prevprice;
let volplunge be volume <= 0.8*(fun pred of volume order time);

Here's the effect on STOCK. (For the moment, look only at the first column
under each of the four virtual attributes shown.)

STOCK
(symbol time price volume) volstable pristable priceincr volplunge vpp
GOOG  1000   10   1100    t         t         t         f          f
GOOG  1006   12   1400    f t       f t       t t       f f        f
GOOG  1012   10   1200    t f t     t f t     f f t     f f f      t
GOOG  1018   13   1182    t f t     f t f     t t t     f f f      f
GOOG  1024   15   1200    t f t     f f f     t t t     f f f      f
GOOG  1030   16   1300    f t t     f f f     t t t     f f f      f
GOOG  1036   11   1100    t f t     t f t     f f f     f f f      f
GOOG  1042   18   1090    t f t     f f f     t t t     f f f      f
GOOG  1048   19   1080    t f t     f f f     t t t     f f f      f
GOOG  1054   20   1070    t f t     f f f     t t t     f f f      f
GOOG  1100   21   1000    t f f     f f f     t t t     f f f      f
GOOG  1106   21    800    f   f     f   f     t   t     t   t      f
GOOG  1112   20    870    f         f         f         f          f
GOOG  1118   21   1000    t         f         t         f          f
GOOG  1124   23   1070    t         f         t         f          f
GOOG  1130   24   1070    t         f         t         f          f
GOOG  1036   20   1070    t         f         t         f          f
GOOG  1142   24    870    f         f         f         f          f
GOOG  1148   26    800    f         f         f         f          f

We can find out if the volume is stable and the price is stable or increasing
over the whole relation:
red and of (volstable and (pristable or priceincr))
This is false (as is  red and of volstable  by itself, and
red and of (pristable or priceincr)  by itself).

But we don't want to know if these hold over the whole relation, but only over
hour-long windows. We need a windowing reduction. We replace  red  above by a
new operator,  redwin(),  which can have a parameter saying how big the window
is. For the moment, let's use an integer count, redwin(10).

let vpp be redwin(10) and of (volstable and (pristable or priceincr))
order time;

Note that redwin() must be controlled by an  order  clause (and it may also
have a group  by  clause).

Two windows are shown above in the second and third columns under volstable,
pristable, priceincr and volplunge. The resulting attribute, vpp, is shown on
the right, with the value for each window shown at the starting entry for the
window.

Note that redwin() wraps around cyclically, unless we write code to stop it.

The idea behind redwin() is that each window is considered to be a separate
relation, and any virtual attribute, especially aggregates from red, equiv,
fun and par, mentioned in a redwin() statement is to be actualized in that
separate relation. Redwin() returns a single value for every window, which
is why it must be a  red .

5. Here's redwin() in a group-by context.
let allPI be redwin(3) and of priceincr order time by symbol;
STOCK
(symbol time price volume) priceincr allPI
GOOG  1000   10   1100       t       f
GOOG  1006   12   1400       t       f
GOOG  1012   10   1100       f       t
GOOG  1018   13   1000       t       t
GOOG  1024   15   1200       t       f  << remember: cyclic >>
GOOG  1030   16   1300       t       f
BALL  1000    2    700       t       f
BALL  1006    3    800       t       f
BALL  1012    1    600       f       t
BALL  1018    1    600       t       f
BALL  1024    2    800       t       f  << remember: cyclic >>
BALL  1030    1    600       f       t

6. We could have a variable window size, determined by an attribute of the
relation.

let ct be redwin(wsize) + of 1 order seq;
let tot be redwin(wsize) + of seq order seq;
A(seq wsize) ct tot
1    3     3   6
2    3     3   9
3    4     4  13
4    2     2   9
5    2     2   6

7. In addition to the counting parameter for  redwin()  we can have a logical
parameter which tells us when to stop.

let firstime be red min of time;
let stop be time >= firstime + 18;
let allPI be redwin(stop) and of priceincr order time by symbol;

Both count and stopping predicate may be passed to redmin() (distinguished by
type), and the logical  or  is taken to determine the window size.

The stopping predicate can be written so as to stop the calculations before
the specified window size is reached.

let vpp be redwin(10,not(volstable and (pristable or priceincr)))
and of (volstable and (pristable or priceincr)) order time;

stops the window, and the  red and of  calculation, as soon as a false value
of the predicate is reached.

An implementation might even be able to use the stopping predicate to skip the
window past the point of failure, since intermediate windows will give false
results.

Post-lecture note (080412).
Let's generalize this to _any_ predicate limiting the window range given by
the size parameter. Thus in a window of size 5 with sequence number s running
within the window from 1 to 5, the predicate  s>1 & s<5  or  2<=s & s<=4
would limit the window to tuples with those sequence numbers. See queryHum.pdf,
Note 9, for an example.

For reasons motivated by that example, we can allow the window size parameter
to be negative as well as positive, and just use the absolute value.

As a pragma to help the implementation know when to start or stop, in the case
of a window predicate-limited to single contiguous subset of the range given
by the size parameter, we could provide side-effect predicates which toggle
when their argument becomes true:  start  and  stop . Thus in the above example
in the predicate  start(2=s) & stop(s=5),  start() would initially be false and
stop() true, and as s progresses from 1 to 5 the predicate would be F,T,T,T,F.

8. Query 2 captures a one-hour period in which the price of a particular stock
increased from 10 to 20 and the trading volume of the stock stayed relatively
stable.

let firstime be red min of time;
let firstvol be red max of if time = firstime then volume else -1;
let volstable be 0.9*firstvol <= volume <= 1.1*firstvol;
let prevprice be if time = firstime then price - 1 else
fun pred of price order time;
let priceincr be price >= prevprice;
let price10 be red max of price = 10;
let price20 be red max of price = 20;
let query2 be redwin(time >= firstime + 60 or time < firstime)
and of (time10 and time20 and volstable and priceincr)
order time by symbol;

STOCK
(symbol time price volume) volstable priceincr query2
GOOG  1000   10   1100    t         t           f
GOOG  1006   12   1400    f         t
GOOG  1012   10   1200    t         f
GOOG  1018   13   1182    t         t
GOOG  1024   15   1200    t         t
GOOG  1030   16   1300    f         t
GOOG  1036   11   1100    t t       f t         f
GOOG  1042   18   1090    t t       t t
GOOG  1048   19   1080    t t       t t
GOOG  1054   20   1070    t t       t t
GOOG  1100   21   1000      t         t
GOOG  1106   21    800      f         t
GOOG  1112   20    870      f t       f t       f
GOOG  1118   21   1000      t f       t t
GOOG  1124   23   1070      t f       t t
GOOG  1130   24   1070      t f       t t
GOOG  1036   20   1070        f         t
GOOG  1142   24    870        t         f
GOOG  1148   26    800        t t       f t     f

Note that  redwin( .. or time < firstime  prevents cycling back.

9. Query 3 captures a more complex trend for each stock: in the last hour, the
volume started high, but after a period when the price increased or remained
relatively stable, the volume plummeted.

We need an automaton to ensure that the volume plummets _after_ the stable
increase.

let firstime be red min of time;
let firstvol be red max of if time = firstime then volume else -1;
let hivol be red max of firstvol > 1000;
let firstprice be red max of if time = firstime then price else -1;
let pristable be 0.9*firstprice <= price <= 1.1*firstprice;
let prevprice be if time = firstime then price - 1 else
fun pred of price order time;
let priceincr be price >= prevprice;
let priceOK be pristable or priceincr;
let volplunge be volume <= 0.8*(fun pred of volume order time);
let automIn be 2*(if priceOK then 1 else 0) +if volplunge then 1 else 0;
relation automQ3(sS,in,eS) <- {(0,0,0),(0,1,0),(0,2,1),(0,3,0),
(1,0,0),(1,1,0),(1,2,1),(1,3,2),(2,0,2),(2,1,2),(2,2,2),(2,3,2)};
relation termQ3(eS) <- {(2)};
makeAutom(in automQ3, in termQ3, in 0, out runauto);
let automCheck be fun runauto of automIn order time;
let query3 be redwin(time >= firstime + 60  or time < firstime)
and of (hivol and red max of automCheck)
order time by symbol;

STOCK
(symbol time price volume) priceOK volplunge query3
GOOG  1000   10   1100    t       f           f
GOOG  1006   12   1400    t t     f f         f
GOOG  1012   10   1200    t f t   f f f       t
GOOG  1018   13   1182    t t t   f f f       t
GOOG  1024   15   1200    t t t   f f f       t
GOOG  1030   16   1300    t t t   f f f       t
GOOG  1036   11   1100    t f t   f f f       t
GOOG  1042   18   1090    t t t   f f f       t
GOOG  1048   19   1080    t t t   f f f       t
GOOG  1054   20   1070    t t t   f f f       t
GOOG  1100   21   1000      t t     f f       t
GOOG  1106   21    800        t       t       f
GOOG  1112   20    870                        f
GOOG  1118   21   1000                        f
GOOG  1124   23   1070                        f
GOOG  1130   24   1070                        f
GOOG  1036   20   1070                        f
GOOG  1142   24    870                        f
GOOG  1148   26    800                        f

10. I have added only one new construct, redwin(), in all the above. (Running
automata follows directly from the programmer-definable funop of [week2p1],
and this is an expected capability, given that Aldat supports funops at all.)
Note that redwin() is possible only because of virtual attributes: it is
conceptually as easy to think of an attribute being actualized on a window as
on a whole relation. Without virtual attributes, all sorts of constructs
would be needed as we see in [DiaoImmGyll:SASE+].

But redwin() was not the first construct I came up with. On my way there I
first produced a much more elaborate and less powerful set of operators. I'd
like to discuss these even though they are replaced by redwin(), in order to
show some of the discovery process. Also, the obsolete facilities might offer
a way to implement redwin().

let w be winsize(win) 3 order seq;
<< shorthand below: 3,4,0 is {(3),(4),(0)} >>
let base be fun + of 1 order seq;
let linear_w be where win

```