On Line Processing of Compacted Relations

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