Revisiting Redundancy and Minimization in an XPath Fragment
Authors
- Benny Kimelfeld (The Hebrew University, Israel)
- Yehoshua Sagiv (The Hebrew University, Israel)
Abstract
Redundancy and minimization of queries are investigated in a well known fragment of XPath that includes child and descendant edges, branches, wildcards, and multiple output nodes. Contrary to a published result, a proposed technique does not guarantee minimality or even non-redundancy, and it is unknown whether a non-redundant query is also minimal. It is shown that for two sub-fragments, non-redundancy and minimality are the same, and can be realized by means of simple (local) tests. The latter property is used to prove that testing non-redundancy is NP-complete.