Artykuł w czasopiśmie
Brak miniatury
Licencja
ClosedAccessDostęp zamknięty
 

Optimizing Tree Patterns for Querying Graph- and Tree-Structured Data

Uproszczony widok
dc.abstract.enMany of today's graph query languages are based on graph pattern matching. We investigate optimization for treeshaped patterns with transitive closure. Such patterns are quite expressive, yet can be evaluated efficiently. The minimization problem aims at reducing the number of nodes in patterns and goes back to the early 2000's. We provide an example showing that, in contrast to earlier claims, tree patterns cannot be minimized by deleting nodes only. The example resolves the M ?/= NR problem, which asks if a tree pattern is minimal if and only if it is nonredundant. The example can be adapted to also understand the complexity of minimization, which was another question that was open since the early research on the problem. Interestingly, the latter result also shows that, unless standard complexity assumptions are false, more general approaches for minimizing tree patterns are also bound to fail in some cases.
dc.affiliationUniwersytet Warszawski
dc.contributor.authorMartens, Wim
dc.contributor.authorNiewerth, Matthias
dc.contributor.authorParys, Paweł
dc.contributor.authorCzerwiński, Wojciech
dc.date.accessioned2024-01-25T16:08:56Z
dc.date.available2024-01-25T16:08:56Z
dc.date.issued2017
dc.description.financeNie dotyczy
dc.description.number1
dc.description.volume46
dc.identifier.doi10.1145/3093754.3093759
dc.identifier.issn0163-5808
dc.identifier.urihttps://repozytorium.uw.edu.pl//handle/item/115015
dc.identifier.weblinkhttps://dl.acm.org/doi/10.1145/3093754.3093759
dc.languageeng
dc.pbn.affiliationcomputer and information sciences
dc.relation.ispartofSIGMOD Record
dc.relation.pages15–22
dc.rightsClosedAccess
dc.sciencecloudnosend
dc.titleOptimizing Tree Patterns for Querying Graph- and Tree-Structured Data
dc.typeJournalArticle
dspace.entity.typePublication