# Equivalence of XML queries

$$\textbf{Problem statement:}$$ Given a set of tree patterns $$\{P,P_1,...,P_k\}$$ where each $$P_i$$ has the same topology as $$P$$ (i.e. $$P_i$$ and $$P$$ have the same sets of nodes and edges excepting the fact that their nodes attributes are different - $$\textit{see example below}$$). Attributes on a node allow to define a search condition of this node, for instance, $$Person[@role='PhD',@started='2020']$$ returns not all $$PhD$$ students but only those who have started their $$PhD$$ at $$2020$$. Moreover, an edge represents a relationship between two nodes, for instance $$Person[@role='supervisor',@gender='femal']\rightarrow Person[@role='PhD']$$ looks for all $$PhD$$ students supervised by woman. My questions are:

a) how to determine whether, for any data tree $$T$$, $$P(T) = P_1(T)\cup ...\cup P_k(T)$$ ? where $$P(T)$$ (resp. $$P_i(T)$$) is the result of evaluating $$P$$ (resp. $$P_i$$) over $$T$$.

b) whether some NPC problem reduces to my problem ?

$$\textbf{Example:}$$ Consider a simple tree pattern $$P=Teacher[@age\in[30,50]]\rightarrow Courses$$ that returns all $$Courses$$ of some $$Teacher$$ whose $$age$$ is between $$30$$ and $$50$$. If we consider the patterns $$P_1=Teacher[@age\in[30,40]]\rightarrow Courses$$ and $$P_2=Teacher[@age\in[40,50]]\rightarrow Course$$ then it is clear that, for any data tree $$T$$, $$P(T)=P_1(T)\cup P_2(T)$$ where $$\cup$$ is used to merge different result sets.

$$\textbf{Note:}$$ I know there exists a bulk of work that studied equivalence of tree patterns but they differ from my work since I consider that patterns have the same topology.

• If you'd like to get an answer here, I suggest formulating the problem in a way that doesn't require any prior knowledge about XML queries. I doubt that the typical audience here is going to know what is going on in the first paragraph of your question. Please define all notation, including what is meant by $\cup$ and $=$ on XML queries (what is the formalization?). What are "attributes conditions"?