On Line Processing of Compacted Relations

In this paper the problem of satisfying the two seemingly contradictory requirements of finding an "optimal" compaction scheme and processing optimally compacted relations on the fly is addressed.

Abstract

Most data base machines use some kind of "filter" that performs unary relational operators (selec-tion and projection) on relations Cl to 71. These filters operate "on the fly " that is, at the speed of the disk, while the relation is being transferred into main memory, Processing time being proportional to relation size, it is therefore important to represent data in the most compacted way. In this paper we address the problem of satisfying the two seemingly contra-dictory requirements: i) finding an "optimal " compaction scheme ii) processing optimally compacted relations on