ملخص: 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 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(2O(|?|)|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.

لغة: إنجليزية