Please use this identifier to cite or link to this item: http://hdl.handle.net/1942/11591
Full metadata record
DC FieldValueLanguage
dc.contributor.authorBjorklund, Henrik-
dc.contributor.authorGELADE, Wouter-
dc.contributor.authorMARTENS, Wim-
dc.date.accessioned2011-02-07T09:30:59Z-
dc.date.availableNO_RESTRICTION-
dc.date.available2011-02-07T09:30:59Z-
dc.date.issued2010-
dc.identifier.citationACM TRANSACTIONS ON DATABASE SYSTEMS, 35(4)-
dc.identifier.issn0362-5915-
dc.identifier.urihttp://hdl.handle.net/1942/11591-
dc.description.abstractIncremental view maintenance for XPath queries asks to maintain a materialized XPath view over an XML database. It assumes an underlying XML database D and a query Q. One is given a sequence of updates U to D, and the problem is to compute the result of Q(U(D)): the result of evaluating query Q on database D after having applied updates U. This article initiates a systematic study of the Boolean version of this problem. In the Boolean version, one only wants to know whether Q(U(D)) is empty or not. In order to quickly answer this question, we are allowed to maintain an auxiliary data structure. The complexity of the maintenance algorithms is measured in, (1) the size of the auxiliary data structure, (2) the worst-case time per update needed to compute Q(U(D)), and (3) the worst-case time per update needed to bring the auxiliary data structure up to date. We allow three kinds of updates: node insertion, node deletion, and node relabeling. Our main results are that downward XPath queries can be incrementally maintained in time O(depth(D) . poly(vertical bar Q vertical bar)) per update and conjunctive forward XPath queries in time O(depth(D) . log(width(D)) . poly(vertical bar Q vertical bar)) per update, where vertical bar Q vertical bar is the size of the query, and depth(D) and width(D) are the nesting depth and maximum number of siblings in database D, respectively. The auxiliary data structures for maintenance are linear in vertical bar D vertical bar and polynomial in vertical bar Q vertical bar in all these cases.-
dc.language.isoen-
dc.publisherASSOC COMPUTING MACHINERY-
dc.subject.otherAlgorithms; Design; Languages; Standardization; Theory; XML; XPath; view maintenance-
dc.titleIncremental XPath Evaluation-
dc.typeJournal Contribution-
dc.identifier.issue4-
dc.identifier.volume35-
local.format.pages43-
local.bibliographicCitation.jcatA1-
dc.description.notes[Bjorklund, Henrik] Umea Univ, Dept Comp Sci, S-90187 Umea, Sweden. [Gelade, Wouter] Hasselt Univ, B-3590 Diepenbeek, Belgium. [Gelade, Wouter] Transnatl Univ Limburg, B-3590 Diepenbeek, Belgium. [Martens, Wim] Tech Univ Dortmund, Fak Informat, D-44227 Dortmund, Germany.-
local.type.refereedRefereed-
local.type.specifiedArticle-
dc.bibliographicCitation.oldjcatA1-
dc.identifier.doi10.1145/1862919.1862926-
dc.identifier.isi000285294300007-
item.fulltextNo Fulltext-
item.validationecoom 2012-
item.contributorBjorklund, Henrik-
item.contributorMARTENS, Wim-
item.contributorGELADE, Wouter-
item.fullcitationBjorklund, Henrik; GELADE, Wouter & MARTENS, Wim (2010) Incremental XPath Evaluation. In: ACM TRANSACTIONS ON DATABASE SYSTEMS, 35(4).-
item.accessRightsClosed Access-
crisitem.journal.issn0362-5915-
crisitem.journal.eissn1557-4644-
Appears in Collections:Research publications
Show simple item record

SCOPUSTM   
Citations

9
checked on Sep 2, 2020

WEB OF SCIENCETM
Citations

7
checked on Jun 29, 2022

Page view(s)

42
checked on May 20, 2022

Google ScholarTM

Check

Altmetric


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.