Security Threats in Web-Powered Databases and Web Portals

Introduction

In this chapter we will focus on the problem of estimating the result of a count query on a very large database, fast. The problem of computing counts of records from a database with given desired characteristics is a common one in the area of decision support systems, online analytical processing (OLAP), and data mining. A typical scenario is as follows: a customer analyst has access to a database of customer transaction information (e.g., customer A bought items B, C, and D at the store at location X), and is interested in discovering patterns that exhibit an interesting or unusual behavior that might lead to possibly profitable insights into the company’s customer behavior. In other words, the company wants to be able to create a model of its customer base (possibly partial), and the better it is able to do that, the more insights it can obtain from the model and more profitable it has the opportunity to be. In this example scenario an analyst would, through an interactive query process, request count information from the database, possibly drilling down in interesting subsets of the database of customer information. It is very important that the results to these queries be returned quickly, because that will greatly facilitate the process of discovery by the analyst. It is also important that the answers to these queries are accurate up to a reasonable degree, although it is not imperative that they are exact. The analyst wants an approximate figure of the result of the query and getting it correct down to the last digit is not necessary.

The methods presented in this chapter are motivated by these observations, that is, the fact that we need great speed coupled with only reasonable accuracy. In the following we present NetCube, a method that can support fast, approximate queries on very large databases. NetCube can fit approximately a database of billions of records in the main memory of a single workstation. There is no “trick” to this—it is due to the fact that what is stored in memory is not the actual data themselves, but only a model of the data. This model is a Bayesian network (BN), which can be used to answer count queries quickly, albeit only approximately. The speed comes from the fact that only the Bayesian network is used to answer the query, and the database is not accessed at query time. The database is accessed only during the one-time preprocessing phase, when a number of BN models are constructed from it.

There are two important considerations relevant to the problem described above: