joint work with Wim Martens, Matthias Niewerth and Paweł Parys

I will consider the problem of minimising tree pattern queries. I will show you the example, which contradicted the long standing conjecture that minimality is the same as nonredundancy. Then I will present how this leads to the \Pi^2_P-completeness of the minimisation problem.