Please use this identifier to cite or link to this item:
http://hdl.handle.net/1942/12114
Full metadata record
DC Field | Value | Language |
---|---|---|
dc.contributor.author | Wu, Yuqing | - |
dc.contributor.author | Van Gucht, Dirk | - |
dc.contributor.author | GYSSENS, Marc | - |
dc.contributor.author | Paredaens, Jan | - |
dc.date.accessioned | 2011-08-17T12:20:00Z | - |
dc.date.available | NO_RESTRICTION | - |
dc.date.available | 2011-08-17T12:20:00Z | - |
dc.date.issued | 2011 | - |
dc.identifier.citation | COMPUTER JOURNAL, 54(7). p. 1091-1118 | - |
dc.identifier.issn | 0010-4620 | - |
dc.identifier.uri | http://hdl.handle.net/1942/12114 | - |
dc.description.abstract | We study the expressiveness of a positive fragment of path queries, denoted Path(+), on documents that can be represented as node-labeled trees. The expressiveness of Path(+) is studied from two angles. First, we establish that Path(+) is equivalent in expressive power to two particular subfragments, as well as to the class of tree queries, a subclass of the first-order conjunctive queries defined over the label, parent-child and child-parent predicates. The translation algorithm from tree queries to Path(+) yields a normal form for Path(+) queries. Using this normal form, we can decompose a Path(+) query into subqueries that can be expressed in a very small fragment of Path(+) for which efficient evaluation strategies are available. Second, we characterize the expressiveness of Path(+) in terms of its ability to resolve nodes in a document. This result is used to show that each tree query can be translated to a unique, equivalent and minimal tree query. The combination of these results yields an effective strategy to evaluate a large class of path queries on documents. | - |
dc.language.iso | en | - |
dc.publisher | OXFORD UNIV PRESS | - |
dc.subject.other | XML; path query; normal form; expressiveness; minimization | - |
dc.title | A Study of a Positive Fragment of Path Queries: Expressiveness, Normal Form and Minimization | - |
dc.type | Journal Contribution | - |
dc.identifier.epage | 1118 | - |
dc.identifier.issue | 7 | - |
dc.identifier.spage | 1091 | - |
dc.identifier.volume | 54 | - |
local.format.pages | 28 | - |
local.bibliographicCitation.jcat | A1 | - |
dc.description.notes | [Gyssens, M] Hasselt Univ, Fac Sci, B-3590 Diepenbeek, Belgium [Gyssens, M] Transnatl Univ Limburg, B-3590 Diepenbeek, Belgium [Wu, YQ; Van Gucht, D] Indiana Univ, Sch Informat & Comp, Bloomington, IN 47405 USA [Paredaens, J] Univ Antwerp, Dept Math & Comp Sci, B-2020 Antwerp, Belgium marc.gyssens@uhasselt.be | - |
local.type.refereed | Refereed | - |
local.type.specified | Article | - |
dc.bibliographicCitation.oldjcat | A1 | - |
dc.identifier.doi | 10.1093/comjnl/bxq055 | - |
dc.identifier.isi | 000292339500007 | - |
item.accessRights | Closed Access | - |
item.fulltext | No Fulltext | - |
item.validation | ecoom 2012 | - |
item.contributor | Wu, Yuqing | - |
item.contributor | Van Gucht, Dirk | - |
item.contributor | GYSSENS, Marc | - |
item.contributor | Paredaens, Jan | - |
item.fullcitation | Wu, Yuqing; Van Gucht, Dirk; GYSSENS, Marc & Paredaens, Jan (2011) A Study of a Positive Fragment of Path Queries: Expressiveness, Normal Form and Minimization. In: COMPUTER JOURNAL, 54(7). p. 1091-1118. | - |
crisitem.journal.issn | 0010-4620 | - |
crisitem.journal.eissn | 1460-2067 | - |
Appears in Collections: | Research publications |
SCOPUSTM
Citations
11
checked on Sep 5, 2020
WEB OF SCIENCETM
Citations
9
checked on Mar 22, 2024
Page view(s)
72
checked on Apr 26, 2023
Google ScholarTM
Check
Altmetric
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.