Selecting and Maintaining Materialized Views for Message Management

Abstract

Electronic messaging has become one of the primary means for the dissemination, exchange and sharing of information. This is facilitated, especially within an organization, by the use of shared folders, which are supported by current electronic messaging systems. We demonstrate that considerable additional flexibility can be achieved by modeling the messaging system as a data warehouse, where each message is a tuple of attribute-value pairs, and each folder is a view on the set of all messages in the messaging system; both user mailboxes and current-day shared folders can be treated as specialized views. Supporting this paradigm in emerging messaging systems, which support thousands of users, makes it imperative to efficiently support a very large number of folders, each defined as a selection view: this is the key difference with conventional data warehouses. We identify two complementary problems concerning the design of such a messaging system. One of the most important tasks of the messaging system concerns the efficient incremental maintenance of eagerly maintained (materialized) folders. This problem for our model of folder definitions is a more general version of the classical point-location problem, and we design an I/O and CPU efficient algorithm for this problem, based on external segment trees and tries. A second important design decision that a messaging system needs to make is the choice of eagerly maintained folders. We present various special cases of the folder-selection problem in the context of messaging systems and present efficient exact/approximation algorithms, and complexity hardness results for them.