Data streaming systems face the possibility of having to shed load in the case of CPU or memory resource limitations. We study the CPU limited scenario in detail. First, we propose a new model for the CPU cost. Then we formally state the problem of shedding load for the goal of obtaining the maximum possible subset of the complete answer, and propose an online strategy for semantic load shedding. Moving on to random load shedding, we discuss random load shedding strategies that decouple the window maintenance and tuple production operations of the symmetric hash join, and prove that one of them — Probe-No-Insert — always dominates the previously proposed coin flipping strategy.

We define a framework for static optimization of sliding window conjunctive queries over infinite streams. When computational resources are sufficient, we propose that the goal of optimization should be to find an execution plan that minimizes resource usage within the available resource constraints. When resources are insufficient, on the other hand, we propose that the goal should be to find an execution plan that sheds some of the input load (by randomly dropping tuples) to keep resource usage within bounds while maximizing the output rate. An intuitive approach to load shedding suggests starting with the plan that would be optimal if resources were sufficient and adding "drop boxes" to this plan. We find this to be often times suboptimal - in many instances the optimal partial answer plan results from adding drop boxes to plans that are not optimal in the unlimited resource case. In view of this, we use our framework to investigate an approach to optimization that unifies the placement of drop boxes and the choice of the query plan from which to drop tuples. The effectiveness of our optimizer is experimentally validated and the results show the promise of this approach.

The problem of mining association rules has attracted a lot of attention in the research community. Several techniques for efficient discovery of association rules have appeared. However, it is nontrivial to perform incremental mining or efficient mining of constrained association rules, in spite of their practical benefits. The research community has recently focused on providing separate solutions for these two problems. Since many believe that constrained mining will be the standard, incremental mining of constrained rules will be necessary. In this paper, a new algorithm, ICAP, for incremental mining of constrained association rules is introduced. The concept of constrained negative border is also introduced and its usage for the maintenance of constrained association rules when new transaction data is added to a transactional database is proposed. This fast incremental mining technique is applied to the constrained association mining algorithm CAP. A key feature of the proposed algorithm is that it requires at most one scan of the original database only if the database insertions cause the constrained negative border to expand. Thus the speedup of incremental mining is combined with the flexibility of the framework of constrained frequent-set queries, CFQs, used for specifying user constraints on the produced association rules. The correctness of the proposed algorithm is studied and a proof of it is given. Several experiments were conducted to measure the relative performance of the new algorithm compared to the single alternative approach available so far, which is rerunning the CAP algorithm on the whole updated database. The results of the experiments show a significant improvement over rerunning CAP in almost all of the cases.