Minimization of Tree Pattern Queries
| Title | Minimization of Tree Pattern Queries |
| Publication Type | Conference Paper |
| Year of Publication | 2016 |
| Authors | Czerwinski, Wojciech, Martens, Wim, Niewerth, Matthias, Parys, Pawel |
| Conference Name | Proceedings of the 35th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems |
| Publisher | ACM |
| Conference Location | New York, NY, USA |
| ISBN Number | 978-1-4503-4191-2 |
| Keywords | Collaboration, Complexity, data deletion, graph databases, Human Behavior, Optimization, pubcrawl, Scalability, tree patterns, trees, XML, XPath |
| Abstract | We investigate minimization of tree pattern queries that use the child relation, descendant relation, node labels, and wildcards. We prove that minimization for such tree patterns is Sigma2P-complete and thus solve a problem first attacked by Flesca, Furfaro, and Masciari in 2003. We first provide an example that shows that tree patterns cannot be minimized by deleting nodes. This example shows that the M-NR conjecture, which states that minimality of tree patterns is equivalent to their nonredundancy, is false. We then show how the example can be turned into a gadget that allows us to prove Sigma2P-completeness. |
| URL | http://doi.acm.org/10.1145/2902251.2902295 |
| DOI | 10.1145/2902251.2902295 |
| Citation Key | czerwinski_minimization_2016 |