"MiniCount: An efficient algorithm for answering count queries using views"
Vassilis Vassalos

Abstract:
We will present MiniCount, the first efficient sound and complete algorithm 
for finding maximally contained rewritings of conjunctive queries with count, 
using conjunctive views with count and conjunctive views without aggregation. 
An efficient and scalable solution to this problem yields significant benefits 
for data warehousing and decision support systems, as well as for powerful 
data integration systems. We first present a naive rewriting algorithm 
implicit in the recent theoretical results by Cohen, Nutt and Sagiv in 2003 
and identify three independent sources of exponential complexity in the naive 
algorithm, including an expensive containment check. Then we present and 
discuss MiniCount and prove it sound and complete. We also present an 
experimental study that shows MiniCount to be orders of magnitude faster than 
the naive algorithm, and to be able to scale to large numbers of views.