Let A be a choice DTD and Q be a query. Then a minimal correct SC annotation of Q can be obtained in time polynomial in the size of Q and A. The correctness of Theorems 5-7 is provided in [26]. The next result shows that it is sufficient to apply rules in a certain normal form, analogously to choiceless DTDs.
