close

Вход

Забыли?

вход по аккаунту

код для вставкиСкачать
Incremental
Maintenance for
Materialized Views over
Semistructured Data
Written By:
Serge Abiteboul
Jason McHuge
Michael Rys
Vasilis Vassalos
Janet L. Wiener
presented By:
Galit Fridman
Outline






Introduction
Incremental Maintenance Approach
Definitions
Incremental Maintenance
Algorithm
Evaluation
Conclusion
Presented by: Galit Fridman
2
Introduction


Database views increase the
flexibility of a database system.
Views are materialized to speed
up querying, when the time is
critical .
Presented by: Galit Fridman
3
Introduction (cont.)

The view contents must be
maintained in order to preserve
consistency with the base data.
Two ways:
• Recomputing the view contents from
the database.
• Computing the incremental updates to
the view, based on the updates to the
database. (used by the new algorithm)
Presented by: Galit Fridman
4
Incremental
Maintenance Approach
For nearly all types of database
updates. It is more efficient to
apply this algorithm to the view
than recompute the view from
the database.
Presented by: Galit Fridman
5
The Algorithm is Based on:

OEM - Object Exchange Model

Lorel Query Language
Presented by: Galit Fridman
6
OEM - Object Exchange
Model
Presented by: Galit Fridman
7
Lorel Query Language


Uses the select..from..where
clauses and additional clause
with.
Provides powerful path
expressions for traversing the
data and rules.
Presented by: Galit Fridman
8
Standard Query

Example 1
select e
from Guide.Restaurant r, r.Entree e
where r.Name = “Baghdad Cafe”
and e.Ingredient = “Mushroom”
The answer is: {&9}
Presented by: Galit Fridman
9
View Specification
Statements



Identify objects within a graph.
Import arbitrary subgraphs.
Add or remove objects appearing in
the view.
Presented by: Galit Fridman
10
View Specification

Example 2
define view FavoriteEntrees as Entrees =
select e
from Guide.Restaurant r, r.Entree e
where exists x in r.Name = “Baghdad Cafe”
and exists y in e.Ingredient = “Mushroom”
with e.Name n ,e.Ingredient I;
Presented by: Galit Fridman
11
Materialized Views


Primary objectsobjects that are
bound to e.
adjunct objects subobjects
discovered by
the with clause.
Presented by: Galit Fridman
12
Update Operations
Insertion and deletions of the
edge.
Denoted: <Ins,o1,L,o2>
<Del,o1,L,o2>
 Change of value of the atomic
object.
Denoted:
<Chg,o1,OldVal,NewVal>

Presented by: Galit Fridman
13
Incremental Maintenance
Algorithm Input
1. View specification statements.
2. Update U: <Ins,o1,L,o2>,
<Del,o1,L,o2>, Chg,o1,Oldval,NewVal>
3. New database state DB’.
4. View instance V.
Presented by: Galit Fridman
14
Incremental Maintenance
algorithm
Basic Structure:
Presented by: Galit Fridman
15
Base Cost For Update
Operations
Presented by: Galit Fridman
16
Database Size
Presented by: Galit Fridman
17
Number of label
occurrences
Presented by: Galit Fridman
18
Length of the form
clause
Presented by: Galit Fridman
19
Bound Variable Position
Presented by: Galit Fridman
20
Selectivity of the where
clause
Presented by: Galit Fridman
21
Conclusion

Advantage:
• The algorithm outperforms
recomputation of the view, even for
large numbers of insert and delete edge
updates.
• Scales well with increasing the
database.

Disadvantage:
• can be expensive as full recomputation
of the view for a single atomic value
change.
Presented by: Galit Fridman
22
1/--страниц
Пожаловаться на содержимое документа