Transcript PowerPoint

Querying and
storing XML
Week 6
XML Updates
February 26-March 1, 2013
1
XML Updates
• Input: an XML tree ΔT and XML update T
• Output: updated XML tree T’ = T + ΔT
February 26-March 1, 2013
QSX
2
Challenges
•
•
•
•
•
The study of the following is still in its infancy:
update languages for XML data
•
XQuery Update Facility: relatively new standard
implementation of XML updates
•
•
native storage of XML data
validation, consistency and integrity
concurrency control for XML “databases”; crash recovery
Question: is there a method to
•
•
•
support updates commonly found in practice?
provide XML query engines with XML update support?
avoid the troubles of concurrency control, consistency checking, etc?
February 26-March 1, 2013
QSX
3
Update Support
• How to update?
•
•
•
Flat streams: overwrite document (slow)
Colonial: SQL updates? (hard to translate)
Native: DOM, proprietary APIs
• How do you know you have not violated schema?
•
•
•
Flat streams: re-parse document
Colonial: need to understand the mapping and translate/maintain
integrity constraints
Native: supported in some systems (e.g., eXcelon)
February 26-March 1, 2013
QSX
4
Atomic updates
February 26-March 1, 2013
QSX
5
Atomic updates
•Basic changes that can be applied to tree
•u ::= insertInto(n,t)
• | insertAsFirstInto(n,t)
• | insertAsLastInto(n,t)
• | insertBefore(n,t)
• | insertAfter(n,t)
• | delete(n)
•
| replace(n,t)
February 26-March 1, 2013
QSX
6
Atomic updates:
insertion
• InsertInto (c,<x><y/></x>)
a
c
b
d
b
x
e
y
February 26-March 1, 2013
QSX
7
Atomic updates:
insertion
• InsertAsFirstInto (c,<x><y/></x>)
a
c
b
x
b
d
e
y
February 26-March 1, 2013
QSX
8
Atomic updates:
insertion
• InsertAsLastInto (c,<x><y/></x>)
a
c
b
b
d
e
x
y
February 26-March 1, 2013
QSX
9
Atomic updates:
insertion
• InsertBefore (c,<x><y/></x>)
a
b
c
x
y
b
d
e
February 26-March 1, 2013
QSX
10
Atomic updates:
insertion
• InsertAfter (c,<x><y/></x>)
a
c
b
x
d
e
b
y
February 26-March 1, 2013
QSX
11
Atomic updates:
deletion
• Delete (c)
a
c
b
b
d
e
February 26-March 1, 2013
QSX
12
Atomic updates:
replace text value
• ReplaceValue (d,"foo")
a
c
b
b
d
e
1234
foo
February 26-March 1, 2013
QSX
13
Atomic updates:
replace subtree
• Replace (c,<x><y/><z/></x>)
a
xc
b
b
y
d
z
e
February 26-March 1, 2013
QSX
14
Atomic updates:
rename
• Rename (c,x)
a
xc
b
b
d
e
February 26-March 1, 2013
QSX
15
Updating XML
stored in relations
February 26-March 1, 2013
QSX
16
Approaches
• We've considered several approaches to
storing XML in relations
•
•
•
•
naive "edge relation:
shared inlining
Dewey Decimal
interval encoding
• How can we update data in these
representations?
• What are the tradeoffs?
February 26-March 1, 2013
QSX
17
Updating XML: naive
• Remember this?
db o1
book
title o3
parent child
nodeId
tag
type
o1
o2
o1
db
ELT
o2
o3
o2
book
ELT
o3
o4
o3
title
TEXT
o2
o5
o4
o5
o6
o5
o2
o7
o7
o8
TEXT
author
o6
o7
o8
Database o4
Managemen
t Systems
author
o2
author o5
author
o7
Ramakrishnao6
n
o8
Gehrke
nodeId
text
TEXT
o4
Database Management
Systems
ELT
o6
Ramakrishnan
TEXT
o8
Gehrke
ELT
February 26-March 1, 2013
QSX
18
Updating XML: naive
•
INSERT INTO Nodes
InsertInto(o5,<foo/>)
VALUE (o9,foo,ELT)
INSERT INTO Edges
VALUE (o5,o9)
title o3
parent child
nodeId
tag
type
o1
o2
o1
db
ELT
o2
o3
o2
book
ELT
o3
o4
o3
title
TEXT
o2
o5
o4
o5
o6
o5
o2
o7
o6
o7
o8
o7
o5
o9
o8
QSX
o9
Database o4
Managemen
t Systems
TEXT
author
author
foo
db o1
book
o2
author o5
author
o7
fooo9
Ramakrishnao6
n
o8
Gehrke
nodeId
text
TEXT
o4
Database Management
Systems
ELT
o6
Ramakrishnan
TEXT
o8
Gehrke
ELT
ELT
February 26-March 1, 2013
19
Updating XML: naive
•
DELETE FROM Nodes
WHERE Delete(o5)
nodeId=o5;
<Trigger...>
DELETE FROM Edges
WHERE parent=o5
OR child=o5;
nodeId tag
parent child
DELETE FROM Nodes
o1
db
o1
o2
WHERE nodeId=o6;
o2
book
o2
o3
DELETE
FROM Text
o3
title
WHERE
nodeId=o6
o3
o4
o2
o5
o4
o5
o6
o5
o2
o7
o7
o8
o8
book
title o3
author
author
o2
author o5
author
o7
type
ELT
ELT
TEXT
Database o4
Managemen
t Systems
TEXT
o6
o7
db o1
Ramakrishnao6
n
o8
Gehrke
nodeId
text
TEXT
o4
Database Management
Systems
ELT
o6
Ramakrishnan
TEXT
o8
Gehrke
ELT
February 26-March 1, 2013
QSX
20
Updating XML: naive
•
UPDATE Nodes
Rename(o2,text)
SET tag='text'
WHERE nodeId=o2
db o1
text
book
title o3
parent child
nodeId
tag
type
o1
o2
o1
db
ELT
o2
o3
o2
book
text
ELT
o3
o4
o3
title
TEXT
o2
o5
o4
o5
o6
o5
o2
o7
o7
o8
TEXT
author
o6
o7
o8
Database o4
Managemen
t Systems
author
o2
author o5
author
o7
Ramakrishnao6
n
o8
Gehrke
nodeId
text
TEXT
o4
Database Management
Systems
ELT
o6
Ramakrishnan
TEXT
o8
Gehrke
ELT
February 26-March 1, 2013
QSX
21
Updating XML: naive
•
UPDATE Text
ReplaceValue(o5,'Raghu')
SET text='Raghu'
WHERE nodeId=o6
title o3
parent child
nodeId
tag
type
o1
o2
o1
db
ELT
o2
o3
o2
book
ELT
o3
o4
o3
title
TEXT
o2
o5
o4
o5
o6
o5
o2
o7
o7
o8
TEXT
author
o6
o7
o8
Database o4
Managemen
t Systems
author
db o1
book
o2
author o5
author
o7
Ramakrishnao6
Raghu
n
o8
Gehrke
nodeId
text
TEXT
o4
Database Management
Systems
ELT
o6
Raghu
Ramakrishnan
TEXT
o8
Gehrke
ELT
February 26-March 1, 2013
QSX
22
Updating XML:
shared inlining
dbdb1
bookbook1
authorauth1
title
Database
Managemen
t Systems
dbID
db1
cod
bookID parentID
e
QSX
auth2
Ramakrishna
n
Gehrke
title
Database Management
Systems
Ramakrishna
book1
n
book1bookID
dbID
authorID
auth1
authorauth2
book1
0
author
Gehrke
February 26-March 1, 2013
23
Updating XML:
shared inlining
• InsertInto(auth1,<foo/>)
Database
Not allowed by
Managemen
schema! t Systems
db1
cod
bookID parentID
e
QSX
auth2
authorauth2
Ramakrishna
n
Gehrke
title
Database Management
Systems
Ramakrishna
book1
n
book1bookID
dbID
authorID
auth1
bookbook1
authorauth1
title
dbID
dbdb1
book1
0
author
Gehrke
February 26-March 1, 2013
24
Updating XML:
shared inlining
dbdb1
•
DELETE FROM authors
Delete(auth1)
WHERE authorId=auth1
bookbook1
authorauth1
title
Database
Managemen
t Systems
dbID
db1
cod
bookID parentID
e
QSX
Ramakrishna
n
Gehrke
title
Database Management
Systems
Ramakrishna
book1
n
book1
Gehrke
book1
Gehrke
February 26-March 1, 2013
book1bookID
dbID
authorID
auth1
auth2
auth2
authorauth2
0
author
25
Updating XML:
shared inlining
dbdb1
• Rename(book1,text)
bookbook1
authorauth1
title
Database
Not allowed by
Managemen
schema! t Systems
dbID
db1
cod
bookID parentID
e
QSX
auth2
Ramakrishna
n
Gehrke
title
Database Management
Systems
Ramakrishna
book1
n
book1bookID
dbID
authorID
auth1
authorauth2
book1
0
author
Gehrke
February 26-March 1, 2013
26
Updating XML:
shared inlining
UPDATE authors
• SET
ReplaceValue(auth1.author,'Raghu'
author='Raghu'
)
title
WHERE authorId=auth1
Database
Managemen
t Systems
dbID
db1
cod
bookID parentID
e
QSX
bookbook1
authorauth1
authorauth2
Ramakrishna
Raghu
n
Gehrke
title
Database Management
Systems
book1 Ramakrishna
Raghu
book1
n
book1
Gehrke
book1
Gehrke
February 26-March 1, 2013
book1bookID
dbID
authorID
auth1
auth1
auth2
auth2
dbdb1
0
author
27
Naive/Shared
inlining: summary
• Rename, replace value, insert relatively
straightforward
•
when allowed by schema (how to check this?)
• Delete can require recursion or triggers
•
•
can avoid this for a non-recursive schema (or delete
of an element with no recursive children)
since there is a fixed upper bound on subtree depth
February 26-March 1, 2013
QSX
28
Updating XML:
Dewey Decimal
• Remember this?
db
tag
type
[]
db
ELT
1
book
ELT
1.1
title
ELT
[]
book
title 1.1
nodeI
D
author
1
1.1.1
TEXT
1.3
1.2
author
1.2
author
1.2.1
1.2.1
Database 1.1.1 Ramakrishna
Managemen
n
t Systems
Gehrke
1.3
1.3.1
1.3.1
ELT
TEXT
author
ELT
TEXT
February 26-March 1, 2013
QSX
29
•
Updating XML:
Dewey Decimal
INSERTInsertAsFirstInto(1.2,foo)
INTO Nodes
VALUE (1.2.0,'foo','ELT')
db
[]
book
title 1.1
author
tag
type
[]
db
ELT
1
book
ELT
1.1
title
ELT
1.1.1
1
1.2
1.3
1.2
nodeI
D
author
TEXT
author
1.2.1
foo 1.2.0
1.2.1
Database 1.1.1 Ramakrishna
Managemen
n
t Systems
Gehrke
1.3
1.3.1
TEXT
author
1.3.1
1.2.0
ELT
ELT
TEXT
foo
ELT
February 26-March 1, 2013
QSX
30
•
Updating XML:
Dewey Decimal
INSERT
INTO Nodes
InsertBefore(1.2,foo)
Problem!
VALUE (1.???,'foo','ELT')
Doesn't fit.
Need to shift labels
db []
(expensive!)
book
title 1.1
author
Managemen
t Systems
type
[]
db
ELT
1
book
ELT
1.1
title
ELT
1.2
1.3
author
TEXT
author
1.2.1
foo1.???
Database 1.1.1
tag
1.1.1
1
1.2
nodeI
D
1.3
1.2.1
Ramakrishna
n
1.3.1
Gehrke
TEXT
author
1.3.1
1.???
ELT
ELT
TEXT
foo
ELT
February 26-March 1, 2013
QSX
31
Updating XML:
Dewey Decimal
UPDATE <nodeIDs>
INSERT INTO Nodes
VALUE (1.2,'foo','ELT')
db
[]
book
title 1.1
author
foo
Database 1.1.1
Managemen
t Systems
tag
type
[]
db
ELT
1
book
ELT
1.1
title
ELT
1.1.1
1
1.3
1.4
1.3
nodeI
D
author
TEXT
author
1.3.1
1.2
1.4
1.3.1
Ramakrishna
n
1.4.1
Gehrke
TEXT
author
1.4.1
1.2
ELT
ELT
TEXT
foo
ELT
February 26-March 1, 2013
QSX
32
•
Updating XML:
Dewey Decimal
DELETE
x from Nodes
Delete(1.2)
nodeI
WHERE PREFIX([1.2],x.nodeId)
D
db
type
[]
db
ELT
1
book
ELT
1.1
title
ELT
[]
book
title 1.1
tag
author
1
1.1.1
TEXT
1.3
1.2
author
1.2
author
1.2.1
1.2.1
Database 1.1.1 Ramakrishna
Managemen
n
t Systems
Gehrke
1.3
1.3.1
1.3.1
ELT
TEXT
author
ELT
TEXT
February 26-March 1, 2013
QSX
33
•
Updating XML:
Dewey Decimal
UPDATE Nodes x
Rename(1,'text')
SET x.tag = 'text'
WHERE x.nodeId = 1
db
tag
type
[]
db
ELT
1
book
text
ELT
1.1
title
ELT
[]
text
book
title 1.1
nodeI
D
author
1
1.1.1
TEXT
1.3
1.2
author
1.2
author
1.2.1
1.2.1
Database 1.1.1 Ramakrishna
Managemen
n
t Systems
Gehrke
1.3
1.3.1
1.3.1
ELT
TEXT
author
ELT
TEXT
February 26-March 1, 2013
QSX
34
•
Updating XML:
Dewey Decimal
UPDATE
Text x
ReplaceValue(1.2.1,Raghu)
SET x.txt = 'Raghu'
WHERE x.nodeId = '1.2'
db
[]
book
title 1.1
author
1
1.2
1.2.1
Database 1.1.1 Ramakrishna
Raghu
Managemen
n
t Systems
nodeI
nodeId
tag
type
tag
type
D
[]
db
ELT
[]
db
ELT
1
book ELT
1
book ELT
1.1
title
ELT
1.1
title
ELT
nodeId 1.1.1
textTEXT
1.1.1
TEXT
Database
Management
1.3
1.2
author
ELT
1.1.1
author
1.2 author
ELT
Systems
1.2.1
TEXT
1.2.1
Raghu
1.2.1 Ramakrishnan
TEXT
1.3 author ELT
1.3.1
Gehrke
1.3 author
ELT
1.3.1
TEXT
1.3.1
1.3.1
TEXT
Gehrke
February 26-March 1, 2013
QSX
35
Updating XML:
interval encodings
• Remember the interval approach:
begi en
par
n
d
1 db 16
2 book 15
3
title
7
6
Database
Managemen
t Systems 5
4
8
author 10
11
author
14
Ramakrishna9
n
12
Gehrke
13
tag
type
db
ELT
1
16
2
15
1
book
ELT
3
6
2
title
ELT
4
5
3
7
10
2
8
9
7
11
14
2
12
13 11
TEXT
author ELT
TEXT
author ELT
TEXT
February 26-March 1, 2013
QSX
36
•
Updating XML:
interval encodings
UPDATE x from Nodes
InsertBefore(8,9,<foo/>)
trickier
SET x.begin=x.begin+2
Problem!
begi en
WHERE x.begin >= 8
par tag
type
Doesn't
fit.
db
n
d
18
1
16 Nodes
UPDATE x from
1 18
db
ELT
to
shift
labels
16
SET x.par2Need
= x.par+2
17
book 15
2
WHERE x.par >=
8
2 17
15 1
1 book
book ELT
ELT
(expensive!)
16
14
12Nodes
title 6
11 author
13
3
6
title
ELT
x 7 author
FROM10
3 UPDATE
3
6 2
2
title
ELT
SET x.end = x.end+2
4
5 3
TEXT
4
5 3
TEXT
8
9
11
9
Database
WHERE foo
x.end
>= 8
Ramakrishna
7 12 2 author ELT
10
8
Managemen
t Systems 5
4
n
14
12
Gehrke
13
15
INSERT INTO Nodes
VALUES (8,9,7,foo,ELT)
7
8
8
10
11
13
12
14
10
9
9
11
14
16
2 author
7
foo
7
7
2 author
author
2
13 13
11
15
ELT
ELT
TEXT
TEXT
ELT
ELT
TEXT
TEXT
February 26-March 1, 2013
QSX
37
Updating XML:
interval encodings
DELETE
x from- easy
Nodes
• Delete(7,10)
WHERE 7 <= x.begin
1 db 16
AND x.end <= 10
2 book 15
3
title
7
6
Database
Managemen
t Systems 5
4
8
author 10
11
author
14
Ramakrishna9
n
12
Gehrke
gaps are fine
13
begi en
par
n
d
tag
type
db
ELT
1
16
2
15
1
book
ELT
3
6
2
title
ELT
4
5
3
7
10
2
8
9
7
11
14
2
12
13 11
TEXT
author ELT
TEXT
author ELT
TEXT
February 26-March 1, 2013
QSX
38
Updating XML:
interval encodings
UPDATE
x
from
Nodes
•
Rename(2,15,"text") - easy
SET x.tag='text'
begi
n
WHERE x.nodeId
= 8
1 db 16
2 text
book 15
3
title
7
6
Database
Managemen
t Systems 5
4
8
author 10
11
author
14
Ramakrishna9
n
12
Gehrke
13
en
par
d
tag
type
1
16
db
ELT
2
15
1
book
text
ELT
3
6
2
title
ELT
4
5
3
7
10
2
8
9
7
11
14
2
12
13 11
TEXT
author ELT
TEXT
author ELT
TEXT
February 26-March 1, 2013
QSX
39
Updating XML:
interval encodings
UPDATE
x from Nodes - easy
• ReplaceVal(8,9,"Raghu")
SET x.text='Raghu'
begi en
par
db
n
d
1
16
WHERE x.nodeId
= 8
2 book 15
3
title
6
Database
Managemen
t Systems 5
4
7
author 10
11
author
14
9
Ramakrishna
8
Raghu
n
12
Gehrke
13
1
16
2
15
1
tag
type
db
ELT
book
ELT
3
6 2
title
ELT
nodeId
text
4 Database
5 3 Management
TEXT
4
7 10 2 Systems
author ELT
8 8
9 Ramakrishnan
7 Raghu TEXT
12
Gehrke
11 14 2 author ELT
12
13 11
TEXT
February 26-March 1, 2013
QSX
40
Updating interval
encodings: summary
• Replace = delete + insert
•
can recycle "gap" left by delete, if inserted tree smaller
• Over time, deletes + inserts lead to "gaps"
•
•
Naive: export DB as XML and re-import (O(n) traversal of
db though).
periodically clean up by finding gaps and shrinking them?
• Some work on leaving "holes" to decrease
amortized cost of insertion
February 26-March 1, 2013
QSX
41
•
•
•
•
Atomic updates:
summary
Atomic updates: primitive change operators on XML data
How can they be implemented?
•
•
•
Shared inlining: using recursive updates/triggers
Dewey: can translate to SQL using prefix, length
Interval: can translate to SQL using <
All of these are expensive for some operations
•
•
Some recent work on "dynamic DDE" avoids this for Dewey approach
at cost of making XPath steps more complex
There has been no comprehensive comparison of these
approaches (AFAIK)
February 26-March 1, 2013
QSX
42
XQuery Update
Facility
February 26-March 1, 2013
QSX
43
Bulk updates
• Atomic updates allow for changing one thing
at a time
•
Widely supported
• But tedious to:
•
•
delete all 2012 students
increase all salaries where employee is in top 10% of sales
• Solution: XQuery Update Facility
•
extends XQuery to allow updating
February 26-March 1, 2013
QSX
44
Compare with SQL
•
•
•
•
Besides queries, SQL has "Data Manipulation Language"
•
•
i.e., bulk updates
which we've already seen in action
Table updates:
•
•
•
INSERT INTO table VALUES r1,...,rn
DELETE FROM table WHERE condition
UPDATE table SET t.a = v ... WHERE condition
But also create/delete tables (CREATE TABLE, DROP
TABLE), add/remove columns, (ALTER TABLE) etc.
For XML, no built-in distinction between table, record, field:
need uniform mechanism for updates
February 26-March 1, 2013
QSX
45
Updating XML
[Tatarinov et al.]
• First paper to propose XQuery extensions
for XML updates
• Idea:
•
•
•
use XPath/XQuery operations to select target nodes of
updates (including conditional tests)
use XQuery to construct subtrees (for insert/replace)
Create a pending update list that is applied in one shot
• XQuery Update Facility uses similar
approach
February 26-March 1, 2013
QSX
46
Example XPathbased updates
db
course
course
cno
title
prereq
cs101
Advanced
Quantum
Query
Languages
course
...
course
course
course
insert node <course>...</course>
into //course[cno='cs101']/prereq
February 26-March 1, 2013
QSX
47
Example XPathbased updates
db
course
course
cno
title
prereq
cs101
Advanced
Quantum
Query
Languages
course
...
course
course
course
delete nodes //course[cno='cs101']/title
February 26-March 1, 2013
QSX
48
XQuery Update
Facility
•Extends queries with updating
expressions
•u
•
•
•
•
•
•
QSX
::= insert node(s) exp
(as first|as last) into path
|
insert node(s) exp
(before|after) path
|
delete node(s) path
|
replace node(s) path with exp
|
replace value of node
path26-March
with exp
February
1, 2013
49
Insert Into
• insert node(s) exp
• (as first|as last) into path
• where exp is an XQuery expression that
constructs subtree value
• and path
is an XPath expression that selects
node(s)
•
•
•
these will be parents of inserted exp
"as first"/"as last" govern where nodes inserted
if not specified, it's up to implementation
February 26-March 1, 2013
QSX
50
Example
• insert node <x><y/></x>
• as first into /a/*
a
c
b
x
x
y
y
b
d
e
x
y
February 26-March 1, 2013
QSX
51
Insert Before/After
• insert node(s) exp
• (before|after) into path
• where exp is an XQuery expression that
constructs subtree value
• and path
is an XPath expression that selects
node(s)
•
•
•
these will be siblings of inserted exp
"as first"/"as last" govern where nodes inserted
if not specified, it's up to implementation
February 26-March 1, 2013
QSX
52
Example
• insert
• before
node <x><y/></x>
/a/b
a
x
y
c
b
b
x
d
e
y
February 26-March 1, 2013
QSX
53
Example:Copy-paste
• for $x
• insert
• before
in /a/c
node $x
/a/*[3]
a
c
b
b
c
d
e
d
e
February 26-March 1, 2013
QSX
54
Other updates
• delete: obvious (delete selected nodes)
• replace: similar to delete + insert
•
replace value allows changing string values
• rename: changes name while keeping
structure fixed
February 26-March 1, 2013
QSX
55
Evaluating complex
updates
• Update evaluation is multi-stage / snapshot:
•
Evaluate query & update expressions to form pending
update list (PUL)
•
•
Check PUL is minimally sensible
•
•
all constructed values are built using old version
e.g. does not rename same node to two different names
Finally, reorder & apply updates
• Good in that it avoids strange behaviors
• But this may not do what you expect!
February 26-March 1, 2013
QSX
56
Example
$x
/
c
a
•
•
•
a
b
a
delete $x//a,
insert <foo>bar</foo>
before $x//a
February 26-March 1, 2013
QSX
57
First collect updates
/
/
c
c
a
a
b
•
•
•
a
a
a
b
a
delete $x//a,
insert <foo>bar</foo>
before $x//a
February 26-March 1, 2013
QSX
58
First collect updates
c
a
/
/
/
c
a
b
a
a
•
•
•
c
a
b
a
foo
a
a
foo
b
foo
a
delete $x//a,
insert <foo>bar</foo>
before $x//a
February 26-March 1, 2013
QSX
59
Then reorder &
apply
c
a
/
/
/
c
a
b
a
a
•
•
•
c
a
b
a
foo
a
a
foo
b
foo
a
delete $x//a,
insert <foo>bar</foo>
before $x//a
February 26-March 1, 2013
QSX
60
XQuery Update
Facility: Transforms
•Queries can perform updates locally
•u
•
•
•
•
•
•
•
QSX
::= insert node(s) exp
(as first|as last) into path
|
insert node(s) exp
(before|after) path
|
delete node(s) path
|
replace node(s) path with exp
|
replace value of node path with exp
|
rename node path as name
February 26-March 1, 2013
61
•
•
•
Transform queries
(hypothetical)
copy $x1 := exp1, ..., $xn := expn
modify u
return exp
• Evaluate exp , bind to $x , ...
• Evaluate exp , bind to $x
• Apply update u
•
1
1
n
n
only $x1... $xn are mutable, other vars cannot be updated
• Evaluate & return exp
•
Key point: No side-effects on database
February 26-March 1, 2013
QSX
62
Example
$x
/
c
a
a
b
a
copy $y := $x/a
modify insert nodes $x/c
as first into $y
return <result>$y</result>
February 26-March 1, 2013
QSX
63
Example: Make copy
$x
$y
/
a
c
a
b
a
b
a
a
copy $x := $doc/a
modify insert nodes $doc/c
as first into $x
return <result>$x</result>
February 26-March 1, 2013
QSX
64
Example: Apply
updates to copy
$x
$y
/
a
c
a
c
a
b
b
a
a
a
No side copy $x := $doc/a
effects on $xmodify insert nodes
$doc/c
as first into $x
return <result>$x</result>
February 26-March 1, 2013
QSX
65
Example: Final result
result
$x
/
a
c
a
c
a
b
b
a
a
a
copy $x := $doc/a
modify insert nodes $doc/c
as first into $x
return <result>$x</result>
February 26-March 1, 2013
QSX
66
Incremental
maintenance of
XML views
February 26-March 1, 2013
QSX
67
Goal: Incremental
Update
February 26-March 1, 2013
QSX
68
Why incremental update?
[Bohannon et al. 2004]
•
•
•
Goal: update external materialized XML tree in response to
changes ΔI to the underlying database
Batch computation: recompute the entire tree from scratch;
•
Incremental computation: compute XML change ΔT
•
•
•
large XML views may take multiple hours or days to produce!
•
Idea: the new view T’ = the old view T +
ΔT
Why? the new view T’ often differs only slightly from the old view T – reuse
partial results computed earlier
Typically more efficient to compute ΔT (small) and update the old view T with ΔT
Incremental computation: an effective technique with a wide
range of applications
February 26-March 1, 2013
QSX
69
Coping with source
updates
•
•
•
•
Problem: the underlying database may be updated constantly (ΔI)
•
e.g. movies database - new movies coming out all the time
Goal: update the published (materialized) XML tree in response to
source changes ΔI -- updating the treatment hierarchies
Incrementally compute XML change ΔT
such that the new view T’ = the old view T + ΔT
February 26-March 1, 2013
QSX
70
Example
Actors
aid
lname
fname
1
Maguir
e
Tobey
2
Movies
Dunst
Kirsten
mid
title
year
11
Spider-Man 2002
32
Elizabethtow
2005
n
Appears
mid
aid
11
1
11
2
32
2
<Movie id="11">
<Title>Spider-Man</Title>
<Year>2002</Year>
<Actor
$Movie
:= id="1">
select mid,title,year
<LName>Maguire</LName>
from Movies
<FName>Tobey</FName>
</Actor>
<Actor id="2">
$id := <LName>Dunst</LName>
$Movie.mid
$year = $Movie.year
$title <FName>Kirsten</FName>
:= $Movie.title $Actors = $Movie.mid
</Actor>
</Movie>
<Movie id="32">
$Actor := select a.aid,a.lname,a.fname
<Title>Elizabethtown</Title>
from actors a, appears app
<Year>1999</Year>
where app.mid=$Actors.mid,app.aid=a.aid
<Actor id="2">
<LName>Dunst</LName>
<FName>Kirsten</FName>
$id := $Actor.aid
</Actor>
$lname := $Actor.lname
</Movie>
$fname
:= $Actor.fname
doc -> Movie*
Movie -> id,title,year,Actors
Actors -> Actor*
Actor -> id,lname,fname
February 26-March 1, 2013
QSX
71
Example
<Movie id="11">
insert Movies(42,Star Wars,1977) <Title>Spider-Man</Title>
<Year>2002</Year>
Actors
<Actor id="1">
<LName>Maguire</LName>
aid
lname fname
<FName>Tobey</FName>
Maguir
$Movie </Actor>
:= select mid,title,year
1
Tobey
<Actorfrom
id="2">
e
Movies
<LName>Dunst</LName>
2
Dunst Kirsten
<FName>Kirsten</FName>
Movies
</Actor>
$id := $Movie.mid
$year = $Movie.year
</Movie>
mid
title
year
$title :=
$Movie.title
<Movie
id="32"> $Actors = $Movie.mid
<Title>Elizabethtown</Title>
11
Spider-Man 2002
<Year>1999</Year>
Elizabethtow
<Actora.aid,a.lname,a.fname
id="2">
Elizabethtow 2005 $Actor := select
32
32
2005
<LName>Dunst</LName>
from
actors a, appears app
n
n
<FName>Kirsten</FName>
where
app.mid=$Actors.mid,app.aid=a.aid
Appears
42
Star Wars 1977
</Actor>
mid
aid
</Movie>
<Movie id="42">
11
1
$id := $Actor.aid
$lname :=<Title>Star
$Actor.lnameWars</Title>
11
2
$fname :=<Year>1977</Year>
$Actor.fname
</Movie>
doc -> Movie*
Movie -> id,title,year,Actors
Actors -> Actor*
Actor -> id,lname,fname
32
2
February 26-March 1, 2013
QSX
72
Example
{+Movies(42,Star Wars,1977)}
Actors
aid
lname
fname
doc -> Movie*
1
Maguir
e
Tobey
+<Movie>...</Movie>
$Movie := select
mid,title,year
from Movies
2
Movies
Dunst
Kirsten
Movie -> id,title,year,Actors
mid
title
year
11
Spider-Man 2002
32
Elizabethtow
2005
n
Appears
42
Star Wars
mid
aid
11
1
11
2
32
2
1977
+@id='42',<Title>Star Wars</Title><Year>1977</Year>...
$id := $Movie.mid
$title := $Movie.title
$year = $Movie.year
$Actors = $Movie.mid
Actors -> Actor*
+ no new actors
$Actor := select a.aid,a.lname,a.fname
from actors a, appears app
where app.mid=$Actors.mid,app.aid=a.aid
Actor -> id,lname,fname
$id := $Actor.aid
$lname := $Actor.lname
$fname := $Actor.fname
February 26-March 1, 2013
QSX
73
More complex
example
insert Actors(3,'Bloom','Orlando')
Actors
aid
lname fname
Maguir
Tobey
e
Dunst Kirsten
Bloom Orlando
title
year
Trickier
need
1
to
find
2
Movies
keys/paths
to
3
mid
insertsubtrees
Appears(32,3)
that
Spider-Man 2002
delete 11Appears(11,2)
need Elizabethtow
to change
32
Appears
QSX
2005
n
mid
aid
11
1
11
2
32
2
32
3
<Movie id="11">
<Title>Spider-Man</Title>
<Year>2002</Year>
$Movie
:= id="1">
select mid,title,year
<Actor
<LName>Maguire</LName>
from Movies
<FName>Tobey</FName>
</Actor>
<!-- deleted -->
$id :=</Movie>
$Movie.mid
$year = $Movie.year
$title<Movie
:= $Movie.title
id="32"> $Actors = $Movie.mid
<Title>Elizabethtown</Title>
<Year>1999</Year>
<Actor
$Actor :=
select id="2">
a.aid,a.lname,a.fname
<LName>Dunst</LName>
from actors a, appears app
where app.mid=$Actors.mid,app.aid=a.aid
<FName>Kirsten</FName>
</Actor>
<Actor id="3">
<LName>Bloom</LName>
$id := $Actor.aid
<FName>Orlando</FName>
$lname :=
$Actor.lname
$fname </Actor>
:= $Actor.fname
</Movie>
doc -> Movie*
Movie -> id,title,year,Actors
Actors -> Actor*
Actor -> id,lname,fname
February 26-March 1, 2013
74
Updating XML
views of relations
February 26-March 1, 2013
QSX
75
View updates
• XML view updates: propagation from XML to
relations
•
•
Input: a mapping σ from DB R to XML T, and XML updates ΔT
Output: updated database R such that T + ΔT = σ (R + ΔR)
• Already hard for relational views
February 26-March 1, 2013
QSX
76
View updates:
hard even for relational views
•
•
•
Input: a relational view definition σ, an instance of relational
database I of schema R, a view V = σ(I), and view updates ΔV
Output: database updates ΔI such that V + ΔV = σ (I + ΔI)
May not be updatable:
•
•
•
•
Schema: R(A, B), S(B, C);
View: ΠAC (R
⨝
S)
View delete: remove (a1, c1).
Not doable without side effect (the deletion of (a1, c2) or (a2, c1))
February 26-March 1, 2013
QSX
77
More on relational
view updates
• May not have a unique answer
•
•
•
•
Schema: R(A, B), S(B, C);
View: ΠAC (R
⨝
S)
View delete: remove (a1, c1).
Not doable without side effect (the deletion of (a1, c2) or (a2,
c1))
February 26-March 1, 2013
QSX
78
Complexity of relational
updates
•
[Buneman et al. 2002]
View updatability problem:
•
•
•
•
given a relational view definition σ, an instance of relational database I of
schema R, a view V = σ(I), and view updates ΔV
decide whether the view is updatable, ie, whether there exists a sideeffect-free database update ΔI such that V + ΔV = σ (I + ΔI)
NP-hard for relational views defined with Projection+Join (PJ) or Join+Union
(JU) only, even for only deletions
Minimal view update problem:
•
•
•
given a relational view definition σ, an instance of relational database I of
schema R, a view V = σ(I), and view insertions (resp. deletions) ΔV
find the smallest database update ΔI such that V + ΔV = σ (I + ΔI)
NP-hard for relational views defined with PJ or JU only, even for only
deletions
February 26-March 1, 2013
QSX
79
XML view updates
•
•
•
•
•
•
Input: an ATG σ from DB R to XML T, and XML updates ΔT
Output: updated database R such that T + ΔT = σ (R + ΔR)
XML updates:
•
•
insert e into p
delete
p
where p: XPath query; e: an XML element/subtree
Suppose that T is stored as edge relations – relational view V
Approach:
•
•
Translate ΔT to ΔV
Resolve the relational view update problem: from ΔV to base relational updates ΔR
February 26-March 1, 2013
QSX
80
Example
delete /Movie[@id=11]/Actor[@id=2]
Actors
aid
lname
fname
2
Movies
Dunst
Kirsten
<Movie id="11">
<Title>Spider-Man</Title>
<Year>2002</Year>
<Actor id="1">
<LName>Maguire</LName>
<FName>Tobey</FName>
</Actor>
<Actor id="2">
<LName>Dunst</LName>
<FName>Kirsten</FName>
</Actor>
</Movie>
<Movie id="32">
<Title>Elizabethtown</Title>
<Year>1999</Year>
<Actor id="2">
<LName>Dunst</LName>
<FName>Kirsten</FName>
</Actor>
</Movie>
delete
Kirsten
Dunst
Maguir
1
Tobey
frome Spiderman?
Another way: delete
mid
title
year
But this
has
sideActors(2,Dunst,Kirsten)
11
Spider-Man 2002
effects!
Elizabethtow
32
2005 way: delete
One
n
Appears
Appears(11,2)
mid
aid
11
1
11
2
32
2
February 26-March 1, 2013
QSX
82
Another tricky one
insert nodes <Actor id='1'>...</Actor
But this violates key
into /Movie[@id='32']
Actors
aid
1
2
Movies
mid1
lname fname
Maguir
Tobey
e
Dunst Kirsten
Maguir
Tobey
title
year
e
Spider-Man 2002
(and has side
effects)
<Movie id="11">
<Title>Spider-Man</Title>
<Year>2002</Year>
...
</Movie>
<Movie id="32">
<Title>Elizabethtown</Title>
<Year>1999</Year>
<Actor id="2">
<LName>Dunst</LName>
<FName>Kirsten</FName>
</Actor>
</Movie>
<Actor
id="1">
<LName>Maguire</LName>
<FName>Tobey</FName>
</Actor>
</Movie>
Another way: insert
Actors(1,Maguire,Tobe
insert
Tobey
Maguire
11
into Elizabethtow
Elizabethtown? y)
32
2005way: add to
One
and Appears(32,1)
n
Appears
Appears
mid
aid
QSX
11
1
11
2
32
2
32
1
February 26-March 1, 2013
83
Summary
• XQuery Update Facility
•
•
allows for bulk updates
semantics somewhat complex
• Updating views of XML stored in relations
•
•
view update: challenging in general
special case: XPath on ATG-defined publishing views
• XML/semistructured updates &
optimizations remain active research topics
February 26-March 1, 2013
QSX
84
Summary;
research areas
• Controlling when/how updates performed
•
•
snapshot (all at once at end) vs. explicit commit
concurrency control
• Dynamic optimization of updates
• Translating XML updates to relational updates
• Typechecking results of updates
• Analyzing when update interferes with query
•
avoiding view recomputation
February 26-March 1, 2013
QSX
85
Next time
• XML typechecking & static analysis
•
•
•
XDuce: A statically typed XML processing language
Static analysis for path correctness of XML queries
Schema-based independence analysis for XML
updates
February 26-March 1, 2013
QSX
86