Type: Research Highlight
Title: Optimizing Tree Patterns for Querying Graph- and Tree-Structured Data
Wojciech Czerwiński, Wim Martens, Matthias Niewerth, Paweł Parys
Available in: PDF
Many 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 e!ciently. 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.
Bio
Wojciech Czerwiński is an assistant professor in Institute of Informatics at the University of Warsaw. He completed his PhD at the University of Warsaw in 2013, then he spend a year on post-doc in University of Bayreuth, Germany.
Wim Martens is a professor on Theoretical Computer Science at the University of Bayreuth, Germany. He completed his PhD in Hasselt University in 2006, visited the DBAI group at the TU Vienna for half a year, and did a post-doc and junior professorship at the TU Dortmund.
Matthias Niewerth is a post-doc at the University of Bayreuth, Germany. He received his PHD from TU Dortmund University in 2015. Matthias Niewerth does research in the field of database theory with focus on semi-structured data.
Paweł-Parys is an assistant professor at the Institute of Informatics, University of Warsaw, Poland. He received his Ph.D. degree in 2012 for a work on fast evaluation of XPath queries in XML documents. Currently his research is focused in the area of higher-order recursion schemes. He has won Best Student Paper Awards at PODS 2009 and Cor Baayen Young Researcher Award 2012.