Thumbnail
Access Restriction
Subscribed

Author Bojaczyk, Mikoaj ♦ Parys, Pawe
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Copyright Year ©2011
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
Subject Keyword Tree with data ♦ XML ♦ XPath
Abstract We consider a fragment of XPath 1.0, where attribute and text values may be compared. We show that for any unary query ϕ in this fragment, the set of nodes that satisfy the query in a document $\textit{t}$ can be calculated in time $O(|ϕ|^{3}|t|).$ We show that for a query in a bigger fragment with Kleene star allowed, the same can be done in time $O(2^{O}(|ϕ|)|t|)$ or in time $O(|ϕ|^{3}|t|log|t|).$ Finally, we present algorithms for binary queries of XPath, which do a precomputation on the document and then output the selected pairs with constant delay.
ISSN 00045411
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 2011-07-01
Publisher Place New York
e-ISSN 1557735X
Journal Journal of the ACM (JACM)
Volume Number 58
Issue Number 4
Page Count 33
Starting Page 1
Ending Page 33


Open content in new tab

   Open content in new tab
Source: ACM Digital Library