Minimization of Tree Patterns
Minimization of Tree Patterns
复制标题
树模式的最小化
DOI：
10.1145/3180281
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
Pawel Parys
中科院分区：
文献类型：
--
作者：
Wojciech Czerwinski;Wim Martens;Matthias Niewerth;Pawel Parys
当今的许多图查询语言都是基于图模式匹配的。我们研究具有传递闭包算子的树形模式的优化。这种模式不仅出现在图数据库的上下文中，而且最初也被研究用于查询树结构数据，在那里它们可以执行子，后代，节点标签和重复测试。最小化问题旨在减少模式中的节点数量，可以追溯到21世纪初。我们提供了一个例子表明，在早期的索赔，树模式不能通过删除节点只最小化。这个例子解决了M =？NR问题，询问树模式是否最小当且仅当它是非冗余的。这个例子可以用来证明最小化是P2-完全的，这解决了另一个问题，这是开放的，因为早期的研究问题。后一个结果表明，除非NP = NP P2，否则最小化树模式的更一般的方法也必然失败。
Many of today’s graph query languages are based on graph pattern matching. We investigate optimization of tree-shaped patterns that have transitive closure operators. Such patterns not only appear in the context of graph databases but also were originally studied for querying tree-structured data, where they can perform child, descendant, node label, and wildcard tests.Theminimizationproblem aims at reducing the number of nodes in patterns and goes back to the early 2000s. 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 prove that minimization is ΣP2-complete, which resolves another question that was open since the early research on the problem. The latter result shows that, unless NP = ΠP2, more general approaches for minimizing tree patterns are also bound to fail in general.