Linear Road Benchmark: STREAM page

STREAM project page for Linear Road Benchmark

Introduction

This page contains information about the Linear Road Benchmark relevant to the STREAM project. More information about the Linear Road Benchmark, including the motivation and specification, can be found here. Currently, this page contains the specification of the benchmark expressed in CQL (Continuous Query Language), a declarative language for continuous queries over streams, developed as part of the STREAM project. The CQL specification makes some minor assumptions in places where the original specification is unclear or imprecise. These assumptions are indicated at the relevant places.

Input

The input to the benchmark contains four "live" streams and some "historical" data. The input streams are described below.

CarLocStr: Stream of car location reports. This forms primary input to the system.

CarLocStr(car_id,        /* unique car identifier       */
          speed,         /* speed of the car            */
          exp_way,       /* expressway: 0..10           */
          lane,          /* lane: 0,1,2,3               */ 
          dir,           /* direction: 0(east), 1(west) */
          x-pos);        /* coordinate in express way   */

AccBalQueryStr: Stream of account-balance adhoc queries. Each query requests the current account balance of a car.

AccBalQueryStr(car_id,   
               query_id);/* id used to associate 
                          * responses with queries      */

ExpQueryStr: Stream of adhoc queries requesting the expenditure of a car for the current day.
```
ExpQueryStr(car_id,
            query_id);
```

TravelTimeQueryStr: Stream of expected-travel-time adhoc queries.

TravelTimeQueryStr(query_id,
                   exp_way,
                   init_seg,      /* initial segment */
                   fin_seg,       /* final segment   */
                   time_of_day,   
                   day_of_week);

Currently, the format of historical data, which is required to answer the adhoc queries above, is not specified. We have presently modeled the historical data using an additional input stream; this modeling will be changed when the complete specification of historical data is provided.

CreditStr: The stream of credits to the account corresponding to a car.
```
CreditStream(car_id, credit);
```

Benchmark Specification

The CQL specification of the benchmark is divided into six parts:

Toll notification.
Toll computation for segments.
Accident detection and notification.
Negative toll generation.
Accounting.
Adhoc query answering.

Instead of presenting the output streams as monolithic queries over the input streams, we use several intermediate streams and relations (see the CQL Technical Report for the definition of the two basic data types in CQL, namely, streams and relations) in the output specification.

Toll Notification

CarSegStr (stream): This is just the input CarLocStr stream, but with the location of the car replaced by the segment corresponding to the location. For simplicity, we assume that each segment is equi-length, and therefore the segment number for a location is just the location (integer-)divided by the length of each segment.
```
SELECT car_id, speed, exp_way, lane, dir, (x-pos/52800) as seg
FROM CarLocStr;
```
CurActiveCars (relation): The relation containing the set of cars "currently" on the freeway: cars that have reported their location in the last 30 seconds.
```
SELECT DISTINCT car_id
FROM CarSegStr [RANGE 30 SECONDS];
```
CurCarSeg (relation): The relation containing the current segment for each car on the freeway. This relation is obtained by computing the latest segment for all the cars (the partition window below), and picking only those cars that are currently active (by joining with CurActiveCars relation above). Note that a segment is identified by the expressway, the direction of travel, and the segment number within the expressway.
```
SELECT car_id, exp_way, dir, seg
FROM CarSegStr [PARTITION BY car_id ROWS 1], CurActiveCars
WHERE CarSegStr.car_id = CurActiveCars.car_id;
```
CarSegEntryStr (stream): Stream of tuples each corresponding to entry of a car into a new segment. A car enters a new segment when a new entry appears in the CurCarSeg relation.
```
ISTREAM (CurCarSeg);
```
Some subtle issues arise when a car exits a segment, and re-enters the same segment; unless we make some additional assumptions not specified in the original benchmark specification, we cannot distinguish between the case of a car continuing in a segment, and that of the car exiting and subsequently re-entering the same segment. Presently, we assume that a car that has exited remains outside the freeway network for atleast 30 seconds, which enables the system to distinguish between the two cases above.
TollStr (stream): Stream of tolls. This is one of the output streams of the benchmark. Each car, on entering a segment, pays a toll determined by the current state of traffic in the segment. The formulation of TollStr below uses a relation, SegToll, that contains the current toll for each segment. The SegToll relation is specified later.
```
SELECT RSTREAM(E.car_id, T.toll)
FROM CarSegEntryStr [NOW] AS E, SegToll as T
WHERE E.exp_way = T.exp_way AND E.dir = T.dir AND E.seg = T.seg;
```
The toll notification stream does not incorporate the frequent-traveler discount as required by the original benchmark specification. Doing so involves "recursion" (since the tolls depend on the previous tolls), and CQL currently does not handle recursion.

Toll Computation for Segments

The toll for each segment depends on the average speed and volume of the cars in the segment, and on the presence of accidents in downstream segments.

SegAvgSpeed (relation) : The average speed of the cars in a segment over the last 5 minutes.

SELECT exp_way, dir, seg, AVG(speed) as speed,
FROM CarSegStr [RANGE 5 MINUTES]
GROUP BY exp_way, dir, seg;

SegVol (relation): Relation containing the number of cars currently in a segment. The relation CurCarSeg is used to determine the cars in each segment.
```
SELECT exp_way, dir, seg, COUNT(*) as volume
FROM CurCarSeg
GROUP BY exp_way, dir, seg;
```
SegToll (relation): Relation containing the toll for each segment. There are no entries in the relation for segments having no toll. A segment is tolled only if the average speed of the segment is less than 40, and if it is not affected by an accident (represented here by the relation AccAffectedSeg which is specified later). If a segment is tolled, its toll is basetoll * (#cars - 150) * (#cars - 150).
```
SELECT S.exp_way, S.dir, S.seg, basetoll*(V.volume-150)*(V.volume-150)
FROM SegAvgSpeed as S, SegVol as V
WHERE S.exp_way = V.exp_way and S.dir = V.dir and S.seg = V.seg
      and S.speed < 40
      and (S.exp_way, S.dir, S.seg) NOT IN (AccAffectedSeg);
```
Pity the lone car of a segment traveling at less than 40!

Accident Detection and Notification

An accident has occurred if a car reports the same location four consecutive times. When an accident is detected by the system, all the cars in 5 upstream segments have to be notified of the accident. Further, 10 upstream segments remain affected for upto 20 minutes after the accident is cleared, and are not tolled.

AccCars (relation): Relation containing cars currently involved in an accident, and the position of the accident. Note that AVG(x-pos) below is just a hack to get the common location of 4 identical location reports of a car involved in an accident.
```
SELECT car_id, AVG(x-pos) AS acc_loc
FROM CarLocStr [PARTITION BY car_id ROWS 4]
GROUP BY car_id
HAVING COUNT DISTINCT (x-pos) == 1;
```
AccSeg (relation): Relation containing the set of segments involved in an accident. This relation is obtained by joining CurCarSeg relation with AccCars relation.
```
SELECT DISTINCT exp_way, dir, seg, acc_loc
FROM CurCarSeg, AccCars
WHERE CurCarSeg.car_id = AccCars.car_id;
```

AccNotifyStr (stream): Output stream notifying an accident to cars currently in the upstream 5 segments from the accident segment. The ISTREAM operator streams a new accident being inserted into AccSeg relation; a new accident tuple is joined with CurCarSeg relation to determine cars in the upstream 5 segments.

SELECT RSTREAM (car_id, acc_loc)
FROM (ISTREAM (AccSeg)) [NOW] AS A, CurCarSeg as S
WHERE (A.exp_way = S.exp_way and A.dir = EAST and S.dir = EAST and 
      S.seg < A.seg and S.seg > A.seg - 5) OR
      (A.exp_way = S.exp_way and A.dir = WEST and S.dir = WEST and 
      S.seg > A.seg and S.seg < A.seg + 5);

AccAffectedSeg (relation): Relation of segments not tolled due to accidents (see SegToll relation). The 10 upstream segments of an accident segment are not tolled until 20 minutes after an accident is cleared. For simplicity, the CQL specification of this relation assumes a fixed relation AllSeg containing the set of all all segments in all the freeways. The relation AccAffectedSeg is specified below as a union of two relations---the relation containing 10 upstream segments of segments currently having an uncleared accident, and the relation containing 10 upstream segments of segments that had an accident cleared within the last 20 minutes.
```
SELECT A.exp_way, A.dir, A.seg
FROM AllSeg AS A, AccSeg AS S
WHERE (A.exp_way = S.exp_way AND A.dir = EAST AND S.dir = EAST AND
       A.seg < S.seg AND A.seg > S.seg - 10) OR
      (A.exp_way = S.exp_way AND A.dir = WEST AND S.dir = WEST AND
       A.seg > S.seg AND A.seg < S.seg + 10)

UNION

SELECT A.exp_way, A.dir, A.seg
FROM AllSeg AS A, DSTREAM ( AccSeg )[RANGE 20 MINUTES] AS S
WHERE (A.exp_way = S.exp_way AND A.dir = EAST AND S.dir = EAST AND
       A.seg < S.seg AND A.seg > S.seg - 10) OR
      (A.exp_way = S.exp_way AND A.dir = WEST AND S.dir = WEST AND
       A.seg > S.seg AND A.seg < S.seg + 10);
```

Negative Toll Generation

Negative tolls are provided to cars on two occasions. First, if a car exits on a segment, the toll for the segment is waived; we model this waiver as a negative toll. Second, if a car exits on any of the five segments upstream of an accident segment, a negative toll of $X is credited to the car's account.

CarExitStr (stream): Stream of events of cars exiting from the freeways. A car has exited if it is no longer "active" (i.e., it has not reported its location in the last 30 seconds). The exiting of cars is determined by applying the DSTREAM operator on the CurActiveCars relation. The relation CurActiveCars does not store the latest segment of the car; this is determined by using the last location report of the car in CarSegStr.
```
SELECT RSTREAM (S.car_id, S.exp_way, S.dir, S.seg)
FROM (DSTREAM (CurActiveCars)) [NOW] AS A,
     CarSegStr [PARTITION BY car_id ROWS 1] AS S
WHERE A.car_id = S.car_id;
```
NegTollStr (stream): Stream of negative tolls to cars exiting on a segment. The amount of the negative toll for an exiting car is equal to the latest charged toll (TollStr) for the car.
```
SELECT RSTREAM (E.car_id, T.toll)
FROM CarExitStr [NOW] AS E, TollStr [PARTITION BY car_id ROWS 1] AS T
WHERE E.car_id = T.car_id;
```

NegAccTollStr (stream): Stream of negative tolls given to cars exiting less than five segments upstream from an accident segment (relation AccSeg).

SELECT RSTREAM (car_id, X)
FROM CarExitStr [NOW] as E, AccSeg as A
WHERE (E.exp_way = A.exp_way AND E.dir = EAST AND A.dir = EAST and 
       E.seg < A.seg AND E.seg > A.seg - 5) OR
      (E.exp_way = A.exp_way AND E.dir = WEST AND A.dir = WEST and 
       E.seg > A.seg AND E.seg < A.seg + 5);

Accounting

AccTransStr (stream): The union of all the transaction of a car account - the "historical" credit stream (CreditStr), the toll stream (TollStr), the negative toll stream (NegTollStr), and the negative toll stream due to accidents (NegAccTollStr).
```
SELECT *
FROM CreditStr

UNION ALL

SELECT car_id, toll AS credit
FROM NegTollStr

UNION ALL

SELECT car_id, toll AS credit
FROM NegAccTollStr

UNION ALL

SELECT car_id, -1 * toll AS credit
FROM TollStr;
```
AccBal (relation): Relation corresponding to the current account balance of each car.
```
SELECT car_id, SUM(credit) AS balance
FROM AccTransStr
GROUP BY car_id;
```

Adhoc Query Answering

AccBalOutStr (stream): Output stream of account balance queries.

SELECT RSTREAM(query_id, B.car_id, B.balance)
FROM AccBalQueryStr [NOW] AS Q, AccBal AS B
WHERE Q.car_id = B.car_id;

ExpOutStr (stream): Output stream of current-day-expenditure adhoc queries.
```
SELECT RSTREAM(query_id, E.car_id, -1 * SUM(credit))
FROM ExpQueryStr [NOW] as Q, AccTransStr[Today Window] as T
WHERE Q.car_id = T.car_id;
```
Currently, all windows in CQL are sliding; it is not possible to express (in a straightforward way) in CQL the window that contains the set of stream tuples seen in the current day, and that slides once every day. The query above uses a user-defined window Today Window to achieve this.
TravelTimeOutStr (stream): Output stream of travel-time-estimate adhoc queries. It seems hard to express this query for even for static relations using SQL. So expressing it in CQL is a daunting task. We need to express this as some user-defined function.

Last modified: May 11, 2003. Please send comments and questions to arvinda@stanford.edu