Show simple item record

dc.contributor.authorRamanan, Prakash
dc.date.accessioned2012-06-19T21:08:41Z
dc.date.available2012-06-19T21:08:41Z
dc.date.issued2012-07
dc.identifier.citationRamanan, P. 2012. "Rewriting XPath queries using materialized XPath views". Journal of Computer and System Sciences. 78 (4): 1006-1025.en_US
dc.identifier.issn0022-0000
dc.identifier.urihttp://hdl.handle.net/10057/5176
dc.identifier.urihttp://dx.doi.org/10.1016/j.jcss.2011.12.001
dc.descriptionClick on the DOI link below to access the article (may not be free).en_US
dc.description.abstractLet XP(/, //, []) be the fragment of XPath 1.0, consisting of queries that involve only the child and descendant axes, and predicates without disjunction or negation (and no wildcard nodetests); these queries can be represented as tree patterns. We consider the problem of rewriting a query Q using a materialized view V. where Q, V is an element of XP(/, //, []). We present more efficient algorithms for the following: (1) Determine if an equivalent rewriting of Q using V exists; find the smallest such rewriting, when it exists. A previously-known algorithm runs in O(vertical bar Q vertical bar(2) + vertical bar Q vertical bar vertical bar V vertical bar) time. For the special case when Q is known to be minimal, we present an O(vertical bar Q vertical bar vertical bar V vertical bar) algorithm. (2) Determine if a (nonempty) contained rewriting of Q using V exists. We present an O(vertical bar Q vertical bar vertical bar V vertical bar) algorithm, compared to the previous O(ver! tical bar Q vertical bar vertical bar V vertical bar(2)) algorithm. We also present a more efficient algorithm for finding a maximal such rewriting, when it exists. Then we extend this result to a subset of XP(/, //, [], *) that allows restricted occurrences of wildcard nodetests.en_US
dc.language.isoen_USen_US
dc.publisherElsevieren_US
dc.relation.ispartofseriesJournal of Computer and System Sciences;2012, v.78, no.4
dc.subjectXMLen_US
dc.subjectXPathen_US
dc.subjectQuery evaluationen_US
dc.subjectViewsen_US
dc.subjectRewritingen_US
dc.subjectHomomorphismen_US
dc.subjectSimulationen_US
dc.titleRewriting XPath queries using materialized XPath viewsen_US
dc.typeArticleen_US
dc.description.versionPeer reviewed
dc.rights.holderCopyright © 2012, Elsevier


Files in this item

FilesSizeFormatView

There are no files associated with this item.

This item appears in the following Collection(s)

Show simple item record