## 3 Improving on Answering Reachability Queries  
We observed that if a label is not divisible by the other label, it is not reachable. Referring to (B) in Figure 1, for example, \(L(H)\) is not divisible by \(L(D)\) and \(H\) is not a descendant of \(D\). Even if these nodes have the same self label 3, they differ in terms of their ancestor nodes' self labels, as in the case of \(self(B)=2\) and \(self(F)=3\). This observation allows us to devise a simpler method of making decisions for unreachable pairs, which is proved in Theorem 1. Theorem 3.1: _If \(L(v)\mod L(w)\) is not \(0\), then \(v\) is not a descendant of \(w\)._  
Proof: In a proof by contrapositive, first we assume that \(v\) is a descendant of \(w\). By Definition 2, because the label is computed recursively, \(L(v)\) contains the label of its parent node \(L(pa(v))\) as a factor, \(L(pa(v))\) contains \(L(pa(pa(v)))\), and so on. This indicates that \(L(v)\) contains \(L(w)\) as a factor, that is, \(L(v)\) is divisible by \(L(w)\). However, the inverse of Theorem 3.1 does not always hold, i.e., if \(L(v)\mod L(w)\) is \(0\), then \(v\) is a descendant of \(w\). Consider the two node pairs (\(E\), \(H\)) and (\(E\), \(P\)) in (B) of Figure 1. \(L(H)\) is divisible by \(L(E)\) and \(H\) is a descendant of \(E\). This is trivial, because a child node label must have its parent node label as a factor. On the other hand, \(L(P)\) is also divisible by \(L(E)\), but \(P\) is indeed not a descendant of \(E\). This occurs because both have the same self labels and their ancestor nodes also have the same self labels (i.e., \(self(B)=self(A)=2\)). Definition 2 leads us to consider the quotient of \(L(P)\div L(E)=2\times 3\) and \(self(E)=3\). If \(P\) is a descendant of \(E\), every factor of the quotient must be larger than or equal to \(self(E)\), because the self label of a child node is larger than or equal to any self labels of its parent nodes. This is not true in this case, which means that \(P\) is not a descendant of \(E\). We formally define this observation in Theorem 2. Theorem 3.2: _Let \(spf(\mathrm{n})\) be the smallest prime factor of a number \(\mathrm{n}\). Let \(\mathrm{q}\) be the quotient of \(L(v)\div L(w)\). Assume that \(L(v)\mod L(w)\) is \(0\). If \(self(w)\leq spf(\mathrm{q})\), then \(v\) is a descendant of \(w\); otherwise, \(v\) is not a descendant of \(w\)._  
Proof: In a direct proof, because \(L(v)\mod L(w)\) is \(0\), we have  
Figure 1: (**A**) is produced by PRM and (**B**) by REP. self labels are in bold. Note that a node label that is in fact to be stored is a single composite number computed by a multiplication of its prime numbers sequence. It can be easily seen that node labels produced by PRM are much bigger than those by REP.  
\[L(v)=L(w)\times\mathrm{q} \tag{1}\]  
There exist two cases for \(\mathrm{q}\). Assume that \(\mathrm{q}\) is a prime number. Consider the case (\(self(w)\leq spf(\mathrm{q})\)). It is trivial that \(spf(\mathrm{q})=\mathrm{q}\) and \(\mathrm{q}\) must be \(self(v)\) by the antecedent and Property 1. Therefore, Equation (1) can be rewritten as \(L(v)=L(w)\times self(v)\). By Definition 2, we have \(w=pa(v)\), which proves the consequent. Now, consider the case (\(self(w)>spf(\mathrm{q})\)). Because \(self(w)\) is the largest factor of \(L(w)\) (by Property 1) and is larger than \(\mathrm{q}\), \(self(w)\) is the largest factor of \(L(v)\), which means that \(self(v)=self(w)\). We now rewrite Equation (1) as \(L(v)=(L(w)/self(v)\times\mathrm{q})\times self(v)\). By Definition 2, there exists a node \(h=pa(v)\) such that \(L(h)=L(w)/self(v)\times\mathrm{q}\). Consider Theorem 1. Because \(L(h)\) mod \(L(w)\) is not 0, \(h=pa(v)\) is not a descendant of \(w\). Therefore, \(v\) is not a descendant of \(w\), which proves the consequent. Assume the second case for Equation (1), where \(\mathrm{q}\) is a composite number.