Incremental MaintenanceofXML Structural IndexesKe Yi1, Hao He1, loana Stanoi2 and Jun Yang2IBMT.J.WatsonResearchCenter
Incremental Maintenance of XML Structural Indexes Ke Yi1 , Hao He1 , Ioana Stanoi2 and Jun Yang1 2 IBM T. J. Watson Research Center
Motivation XML is gaining tremendously in popularity inrecent years Used to represent many kinds of dataMajor DB vendors are rushing to incorporatesolutions for native XML repositories andretrievalIBM DB2, Oracle , Microsoft SQL ServerTamino, Natix, X-Hive,
Motivation ⚫ XML is gaining tremendously in popularity in recent years ⚫ Used to represent many kinds of data ⚫ Major DB vendors are rushing to incorporate solutions for native XML repositories and retrieval ⚫ IBM DB2, Oracle , Microsoft SQL Server ⚫ Tamino, Natix, X-Hive,
Overviewpapersectionsection.titletitlesectionsection“experiments"exp"intro"Igorithmtitleexptitleorithmtproof"A(k)-index""1-index"aboutproofaboutuses
Overview paper section title algorithm “1-index” proof section title “A(k)-index” proof uses algorithm section “experiments” about about title section title “intro” exp exp
Label Path Expressionspaper/paper/section/algorithmsectionsectiontitletitlesectionsection“experiments"XL"intro"lgorithmtitleexptitleorithmproof“A(k)-index"“1-index"aboutproofaboutuses
Label Path Expressions paper section title algorithm “1-index” proof section title “A(k)-index” proof uses algorithm section “experiments” about about title section title “intro” exp exp /paper/section/algorithm
Structural IndexesWhy do we need them?Speedup the evaluation of path expressions Provides a structural summary of the data graphStructural indexesDataGuide [Goldman & Widom 97]1-index [Milo & Suciu 99]A(k)-index [Kaushik et al. 02], D(k)-index [Qun et al. 03]M(k)-index [He & Yang 04]Integration ofstructural indexes andinverted lists[Kaushik et al. 04]FocusonmaintenanceHas a major effect on index efficiencyRemainsanoverlookedissue
Structural Indexes ⚫ Why do we need them? ⚫ Speedup the evaluation of path expressions ⚫ Provides a structural summary of the data graph ⚫ Structural indexes ⚫ DataGuide [Goldman & Widom 97] ⚫ 1-index [Milo & Suciu 99] ⚫ A(k)-index [Kaushik et al. 02], D(k)-index [Qun et al. 03], M(k)-index [He & Yang 04] ⚫ Integration of structural indexes and inverted lists [Kaushik et al. 04] ⚫ Focus on maintenance ⚫ Has a major effect on index efficiency ⚫ Remains an overlooked issue