PAPER:          ~/research/db/message/paper.ps
ABSTRACT:       ~/research/db/message/paper.abs

FILE:    message.ps
AUTHORS: Himanshu Gupta and Divesh Srivastava
TITLE:  Selecting and Maintaining Materialized Views for Message Management
YEAR:     1998
CITATION: technical report
KEYWORDS: view maintenance, view selection, message management, data warehouse



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.