-1
$\begingroup$

$\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.

Thank you in advance

$\endgroup$
3
  • 2
    $\begingroup$ 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"? $\endgroup$
    – D.W.
    Jan 7 at 21:03
  • $\begingroup$ Thank you for your suggestion, I revised my question by adding more clarification and definitions. I hope this will allow audience responding my question $\endgroup$
    – mahou_2019
    Jan 8 at 11:07
  • 1
    $\begingroup$ I don't know what the syntax "Person[@role=′PhD′,@started=′2020′]" means. I think you need to give a self-contained formalization of queries. $\endgroup$
    – D.W.
    Jan 8 at 19:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.