Updates for Structure Indexes
- Raghav Kaushik ,
- Philip Bohannon ,
- Jeffrey F. Naughton ,
- Pradeep Shenoy
VLDB |
Published by Very Large Data Bases Endowment Inc.
The problem of indexing path queries
in semistructured/XML databases has re-
ceived considerable attention recently, and
several proposals have advocated the use of
structure indexes as supporting data struc-
tures for this problem. In this paper, we
investigate ecient update algorithms for
structure indexes. We study two kinds of
updates | the addition of a subgraph, in-
tended to represent the addition of a new
le to the database, and the addition of
an edge, to represent a small incremental
change. We focus on three instances of
structure indexes that are based on the no-
tion of graph bisimilarity. We propose al-
gorithms to update the bisimulation parti-
tion for both kinds of updates and show how
they extend to these indexes. Our experi-
ments on two real world data sets show that
our update algorithms are an order of mag-
nitude faster than dropping and rebuilding
the index. To the best of our knowledge,
no previous work has addressed updates for
structure indexes based on graph bisimilar-
ity.
All articles published in this journal are protected by copyright, which covers the exclusive rights to reproduce and distribute the article (e.g., as offprints), as well as all translation rights. No material published in this journal may be reproduced photographically or stored on microfilm, in electronic data bases, video disks, etc., without first obtaining written permission from Very Large Data Bases Endowment Inc.