Parametric rectangles: A model for spatiotemporal databases

In this dissertation, we propose parametric rectangles—cross products of intervals whose end points are functions of time—as a new data model for representing, querying, and animating spatiotemporal objects with continuous and periodic change. Parametric rectangles are a more natural representation of moving objects than moving points, which is the only other representation of moving objects for which fast indexing methods were previously described. Moreover, moving points are defined only between “now” and +∞, whereas parametric rectangles can have arbitrary time interval durations. We prove that the model is closed under relational algebra and new spatiotemporal operators and that relational algebra queries can be evaluated in PTIME in the size of any input database for both non-periodic parametric rectangles and periodic (with some restriction) parametric rectangles. Finally, we also describe the implementation in our PReSTO database system. We also describe an indexing method for parametric rectangles. The method extends R-trees, with the following important modifications among others: (i) definition of parametric rectangle trees, or PR-trees; (ii) searching a PR-tree for intersection queries; (iii) insertion into PR-trees; (iv) deletion from PR-trees. These modified operations need new algorithms for finding a minimum bounding parametric rectangle (MBPR) of a set of parametric rectangles and a new insertion and splitting criteria and algorithms. Experiments show that PR-trees provide a significant improvement over R-trees for intersection queries with moving rectangles