Active Database Selection Predicate Indexing Using Interval Skip Lists

A selection predicate index for an active database is a data structure that can efficiently find all the selection predicates of active database rules that match a particular data item. We have developed selection predicate indexing strategies based on both the interval binary search tree (IBS -tree) and the interval skip list (IS-list).

Interval skip lists and interval binary search trees are data structures for finding all intervals that overlap a point. They were invented for use in a selection predicate index for active database rule condition testing. But they have many other potential uses. Interval skip lists are simpler to implement than balanced interval binary search trees, so we recommend interval skip lists when a balanced interval index is needed that supports dynamic insertion, search and deletion.

• Paper on selection predicate indexing using interval skip lists A revised version of this has been published, with the following reference citation:

Hanson, E. and T. Johnson, "Selection Predicate Indexing for Active Databases Using Interval Skip Lists," Information Systems, vol. 21, no. 3, pp. 269-298, 1996.

These papers contains a detailed description of IS-list algorithms.

• ISlist.tar A tar file containing C++ source code for IS-lists. Click on the link to copy the file, and name your copy "ISlists.tar". Create a directory to hold the code and put the tar file into it. Then untar the file using tar xvf ISlist.tar and read the README file. Typing make will compile a sample program. If you download the code, please send an email to hanson@cise.ufl.edu with a sentence or two about what you plan to do with it.
• For a discussion of selection predicate indexing using interval binary search trees, see Hanson et al. A predicate matching algorithm for database rule systems. In Proceedings of the ACM SIGMOD Conference, pages 271-280, May 1990.