  The proliferation of imprecise data has motivated both researchers and the
database industry to push statistical techniques into relational database
management systems (RDBMSs). We study algorithms to maintain model-based views
for a popular statistical technique, classification, inside an RDBMS in the
presence of updates to the training examples. We make three technical
contributions: (1) An algorithm that incrementally maintains classification
inside an RDBMS. (2) An analysis of the above algorithm that shows that our
algorithm is optimal among all deterministic algorithms (and asymptotically
within a factor of 2 of a nondeterministic optimal). (3) An index structure
based on the technical ideas that underlie the above algorithm which allows us
to store only a fraction of the entities in memory. We apply our techniques to
text processing, and we demonstrate that our algorithms provide several orders
of magnitude improvement over non-incremental approaches to classification on a
variety of data sets: such as the Cora, UCI Machine Learning Repository data
sets, Citeseer, and DBLife.
