SELECTIVITY ESTIMATION OF TEMPORAL DATA MANIPULATIONS

Temporal relations possess several characteristics that distinguish th em from conventional snapshot relations. First, for each instance of t he surrogate (entity) there is a set of time-ordered tuples. Second, s urrogate instances may arrive and depart in some time-dependent manner . Third, the surrogate instance may arrive and depart more than once, thus creating gaps (null values) within its history. Lastly, the value of the temporal attribute may also be time-dependent. Conventional me thods of estimation are incapable of providing good approximations of the cost of various temporal operations, even for those involving sele ctions on a single relation. The problem is more acute in the case of join operations, because selectivities on time interval intersections have to be estimated. We propose a practical, yet theoretically sound model to characterize the changes of temporal relations. From this mod el, estimates of the cardinalities of various unary and binary operati ons are derived. Simulation results show that the proposed estimates a re both robust and superior to conventional estimates.