Towards Self-Indexing Relational Databases

In this paper, we present methods for compacting and self-indexing the tables of a relational database. This means we replace both the data and the indexes for a unique succinct data structure. This new compact representation uses less space than the plain text of the database. We implemented the necessary machinery to solve search and join operations without decompressing the database. A self-indexed database with this method uses close to 90% of the plain representation while supporting some relational queries and full text searches. When compared to SQlite3+FTS, our representation produces several times smaller databases and faster searches. Extracting the text from the compact representation is slower than SQlite3+FTS, and hence our approach is more useful for selective queries. To cope with this drawback we provide a way to improve the extraction speed at the cost of using more memory. Finally, we provide a large set of experimental results characterizing the memory and time performance of our proposal.