Incremental View Maintenance

Introduction

We can treat views as functions in programming. It essentially summarizes a query operation. There are however, some differences between virtual view and materialized view.

The syntax for creating view is very similar to that of a table

Virtual ViewMaterialized View

CREATE VIEW V AS 
SELECT G, SUM(A) AS S
FROM R
GROUP BY G

1
2
3

CREATE MATERIALIZED VIEW V AS 
SELECT G, SUM(A) AS S
GROUP BY G

Virtual View vs Materialized View

Virtual view is simply a shortcut for writing out a specific query, and therefore, its results are not stored on persistent storage (i.e. materialized). On the other hand, materialized views are actually be written onto disks, and therefore has actual performance implication (improvements). However, this means that whenever there are updates done to the source tables (or associated tables), we must also update materialized view to keep their data consistent. This is not an issue for virtual views.

Materialized View Maintenance

To address the problem mentioned in this section. We have to update the materialized view whenever a source table is updated.

Notation

V: The materialized view
R: The source table
\(\Delta R^{+}\): The set of tuples inserted into R
\(\Delta R^{-}\): The set of tuples removed from R
\(\Delta V^{+}\): The set of tuples to be inserted into V
\(\Delta V^{-}\): The set of tuples to be deleted from V violate

Delete and Recompute V

A very intuitive approach would be to remove everything from V and recompute V with new state of R. This however, is very expensive because the runtime is not proportional to the size of updates being made to R. Instead, the runtime is proportional to the size of table R.

Example

View Creation

CREATE MATERIALIZED VIEW V AS 
SELECT G, SUM(A) AS S
FROM R 
GROUP BY G

Table Update Operation

INSERT INTO R VALUES (...)
INSERT INTO R VALUES (...)
DELETE FROM R WHERE (...)
COMMIT

View Update Operation

DELETE FROM V 
WHERE true

INSERT INTO V 
    (SELECT G, SUM(A) AS S
    FROM R
    GROUP BY G)

Incremental Maintanence

Definition

Self maintained materialized view: a self maintained materialized view is called self maintained if it can compute the next state of the view with just the current state of the view

Example

Note

\(choose(a,b)\) returns a if a is not null, and returns b is a is null
\(n0(a)\) returns a if a is not null, and returns 0 if a is null

Assume we have the following materilized view.

CREATE MATERIALIZED VIEW V AS 
SELECT G, SUM(A) AS S
FROM R
GROUP BY G

The computation of \(\Delta V^{+}\) and \(\Delta V^{-}\) is as followed:

-- whatever changes needed to be added
WITH RGplus AS
(SELECT G, SUM(A) AS S
FROM DELTA_R+
GROUP BY G)

-- whatever changes needed to be deleted
RGMinus AS
(SELECT G, SUM(A) AS S
FROM DELTA_R-
GROUP BY G)


RGnet AS
(SELECT 

-- we only need either G from p.G or s.G to be the G
choose(p.G, m.G) AS G, 

-- RGplus - RGmius: if it didn't appear in RGplus, p.S will be 0, and the same for RGminus
n0(p.S) - n0(m.S) AS S

-- full outer join on G. This will capture everything even if right does not have a tuple with the same G on the left, and vise versa
FROM RGplus AS p FULL OUTER JOIN RGminus AS m ON p.G = m.G)

DELTA_V- AS 
(SELECT * FROM V
WHERE G IN (SELECT G FROM RGnet))

DELTA_V+ AS
(SELECT r.G AS G, n0(V.S) + r.S AS S
-- We're using a right outer join here because 
FROM (V RIGHT OUTER JOIN RGnet AS r ON V.G=r.G))

Eager vs Deferred

	Eager	Deferred
Snapshop 0	\(V^{0} = V(R_{1}^{0}, ..., R_{n}^{0})\)
\(\Delta V^{+}\)	\(\Delta V^{+} = f^{+}(\Delta R_{1}^{+}, ..., \Delta R_{n}^{-}, \Delta R_{1}^{-}, ..., \Delta R_{n}^{-}, ... V^{0}, R_{1}^{0}, ..., R_{n}^{0})\)	\(\Delta V^{+} = f^{+}(\Delta R_{1}^{+}, ..., \Delta R_{n}^{-}, \Delta R_{1}^{-}, ..., \Delta R_{n}^{-}, ... V^{0}, R_{1}^{1}, ..., R_{n}^{1})\)
\(\Delta V^{-}\)	\(\Delta V^{-} = f^{-}(\Delta R_{1}^{+}, ..., \Delta R_{n}^{-}, \Delta R_{1}^{-}, ..., \Delta R_{n}^{-}, ... V^{0}, R_{1}^{0}, ..., R_{n}^{0})\)	\(\Delta V^{-} = f^{-}(\Delta R_{1}^{+}, ..., \Delta R_{n}^{-}, \Delta R_{1}^{-}, ..., \Delta R_{n}^{-}, ... V^{0}, R_{1}^{1}, ..., R_{n}^{1})\)
State used for computation	Prior State (State 0)	Current State (State 1)
Maintenance timing	Prior to changes made to the table	Anytime we want