Incremental Computation of Queries

TitleIncremental Computation of Queries
Publication TypeJournal Article
Year of Publication2009
AuthorsGuozhu Dong, Jianwen Su
KeywordsComputer Communication Networks, computer imaging, database management, Information Storage and Retrieval, information systems applications, Multimedia Information Systems, pattern recognition and graphics, vision
Abstract

A view on a database is defined by a query over the database. When the database is updated, the value of the view (namely the answer to the query) will likely change. The computation of the new answer to the query using the old answer is called incremental query computation or incremental view maintenance. Incremental computation is typically performed by identifying the part in the old answer that need to be removed, and the part in the new answer that need to be added. Incremental computation is desirable when it is much more efficient than a re-computation of the query. Efficiency can be measured by computation time, storage space, or query language desirability/availability, etc. Incremental computation algorithms could use auxiliary relations (in addition to the query answer), which also need to be incrementally computed. Two query languages can be involved for the incremental query computation problem. One is used for defining the view to be maintained, and the other for describing the incremental computation algorithm. For relational databases, the two languages can be relational algebra, SQL, nested relational algebra, Datalog, SQL embedded in a host programming language, etc.

Full Text

Additional Resources