1View Self-MaintenanceCPS 296.1Topics in Database Systems2Self-maintainable views• A view is self-maintainable if it can be maintained without accessing the base tables– That is, using just the base table deltas and the old content of the view itself• Advantages of self-maintainable views– Efficiency: no need to access base tables– Simplicity: no problem with changing base table states3Examples• Self-maintainable– V = σpR• ∇V = σp(∇R), ∆V = σp(∆R)– V = max(R) w.r.t. ∆R• ∇V = V, ∆V = max(V, ∆R)• Not self-maintainable– V = R >< S w.r.t. insertions• ∆V = (∆R >< S) ⊕ (R >< ∆S) ⊕ (∆R >< ∆S)• What about deletions?– V = max(R) w.r.t. ∇R•If V ⊆∇R, then V must be recomputed as max(R)4Making a view self-maintainable• If V is not self-maintainable, add a set of auxiliary views A such that V and A taken together can be maintained without accessing any base tables– That is, using just the base table deltas and the old content of V and A itself•Example– V = max(R) is not self-maintainable– Add auxiliary view A = R– V and A together are self-maintainable– Why not just A = second_max(R)?5A more interesting example• Store(store_id, city, state, manager)• Sale(sale_id, store_id, day, month, year)• Line(line_id, sale_id, item_id, price)• Item(item_id, item_name, category, supplier)• V = πmanager, month, sale_id, line_id, item_id, item_name, priceσstate = “CA” AND year = 1996 AND category = “toy”(Store ><store_idSale ><sale_idLine ><item_idItem)– Not self-maintainable because of joins6Naïve approach• Add auxiliary views that simply copy base tables– AStore= Store– ASale= Sale– ALine= Line– AItem= Item• Implemented by most commercial data warehouses• Certainly correct, but very inefficient– All copies are self-maintainable by themselves– V is maintainable (even computable) from these copies27A smarter approach• V = πmanager, month, sale_id, line_id, item_id, item_name , priceσstate = “CA” AND year = 1996 AND category = “toy”(Store ><store_idSale ><sale_idLine ><item_idItem)• Push selection/projection into auxiliary views– AStore= πstore_id, manager σstate = “CA”Store– ASale= πsale_id, store_id, month σyear = 1996 Sale– ALine= Line– AItem= πitem_id, item_name σcategory = “toy”Item• Correct, and less inefficient– All select-project views are self-maintainable themselves– V is maintainable (even computable) from these views8More information• Key and foreign-key constraints• Insert/delete/update patterns– Append-only tables, updateable columns, etc.• Store(store_id, city, state, manager)• Sale(sale_id, store_id, day, month, year)• Line(line_id, sale_id, item_id, price)• Item(item_id, item_name, category, supplier)– Also, columns referenced in selection/join conditions are not updated9Better auxiliary viewsGiven the additional constraints• AStore= πstore_id, manager σstate = “CA”Store– Same as before• ASale= πsale_id, store_id, month σyear = 1996 Sale><store_idAStore– Note the extra semijoin• AItem= πitem_id, item_name σcategory = “toy”Item– Same as before•NoALineneeded10Why the extra semijoin?ASale= (πsale_id, store_id, month σyear = 1996 Sale) ><store_idAStore• Sale deltas do not need to be joined with Sale• Line and Item deltas are always joined with Sale and Store together– Computable from ASale><store_id AStore(semijoin does not hurt)• ∆Store cannot join with existing Sale tuples– Because every existing Sale references an existing store_id• ∇Store cannot join with existing Sale tuples– Because if it does, it would violate the foreign-key constraint– If it cascades, join with ASaleto find sale_id’s to delete from V11Why no ALine?• Line deltas do not need to be joined with Line• ∆Item and ∆Sale cannot join with existing Line tuples– Because every existing Line references an existing item_id and an existing sale_id• ∇Item and ∇Sale cannot join with existing Line tuples– Because if they do, they would violate the foreign-key constraints– If they cascade, delete from V deleted item_id’s and sale_id’s• Store deltas cannot join with existing Line tuples– Because they cannot even join with existing Sale tuples12What about updates?• In most view maintenance literature, an update is treated as a deletion followed by an insertion• Approach becomes problematic if we want to exploit foreign-key constraints• Example: updating Store.manager– ∇Store = [123, “Fremont”, “CA”, “Amy”]– ∆Store = [123, “Fremont”, “CA”, “Ben”]– Applying ∇Store and ∆Store separately would temporarily violate the foreign-key constraint from Sale.store_id to Store.store_id! Must treat update as one operation313Characterizing updates• Exposed update– Changes the value of a column referenced in select/join conditions of the view– May cause insertion into or deletion from the view• Protected update– Not exposed, but changes the value of a column that is included in the final projection of the view– Causes the view column to be updated• Ignorable update– Neither exposed nor protected– No effect on the view14Auxiliary views re-examined• Assume no exposed updates• For protected updates on Sale, Item, or Line, simply update all V tuples with the affected sale_id’s, item_id’s, or line_id’s• For protected updates on Store, join with ASaleto find all sale_id’s associated with the updated stores, and then update V tuples with these sale_id’s15What if exposed updates are allowed?• Say Sale.year may be updated• Must add auxiliary viewALine= πline_id, sale_id, item_id, price Line><item_idAItem– Any Line can be a 1996 sale after a Sale.year update16Self-maintenance algorithm• How to generate definitions for auxiliary views• How to maintain the original view• How to maintain the auxiliary views• Quass et al. “Making Views Self-Maintainable for Data Warehousing.” PDIS, 199617Join graph of a view•Node R: base table R• Directed edge R → S: join condition of the form R.A = S.K, where K is a key of S– The edge is further annotated with RI if there is a foreign-key constraint from R.A to S.KLineSaleStoreItemRIRIRI18Dep(R)•Dep(R) = { S | there is an edge R → S annotated with RI, and S has no exposed updates }•Example– Dep(Store) = ∅– Dep(Sale) = { Store }– Dep(Item) = ∅–
View Full Document
Unlocking...