Database Reference
In-Depth Information
as a node test and that neither union nor qualifier is supported. Therefore,
we have to explore more general XPath fragments for which satisfiability is
tractable under fixed DTDs. Second, we would like to consider more powerful
schema languages such as XML Schema and RELAX NG. In particular, the
algorithms in Sections 4 and 5 requires several modifications so that they handle
element types supported by such schema languages. On the other hand, the NP-
completeness shown in Sect. 3 still holds under such schema languages. Finally,
the algorithms shown in this paper has not been implemented yet. We need to
implement them and make experiments on the eciency and the availability of
the algorithms.
Acknowledgement.
The author would like to thank Prof. George H. L.
Fletcher for discussions on this topic.
References
1. Benedikt, M., Fan, W., Geerts, F.: Xpath satisfiability in the presence of dtds.
Journal of the ACM 55(2) (2008)
2. Bruggenmann-Klein, A., Wood, D.: One-unambiguous regular languages. Informa-
tion and Computation 142(2), 182-206 (1998)
3. Figueira, D.: Satisfiability of downward xpath with data equality tests. In: Proc.
PODS, pp. 197-206 (2009)
4. Geerts, F., Fan, W.: Satisfiability of xpath queries with sibling axes. In: Bierman,
G., Koch, C. (eds.) DBPL 2005. LNCS, vol. 3774, pp. 122-137. Springer, Heidelberg
(2005)
5. Hidders, J.: Satisfiability of xpath expressions. In: Lausen, G., Suciu, D. (eds.)
DBPL 2003. LNCS, vol. 2921, pp. 21-36. Springer, Heidelberg (2004)
6. Ishihara, Y., Shimizu, S., Fujiwara, T.: Extending the tractability results on xpath
satisfiability with sibling axes. In: Lee, M.L., Yu, J.X., Bellahsene, Z., Unland, R.
(eds.) XSym 2010. LNCS, vol. 6309, pp. 33-47. Springer, Heidelberg (2010)
7. Lakshmanan, L.V.S., Ramesh, G., Wang, H., Zhao, Z.J.: On testing satisfiability
of tree pattern queries. In: Proc. VLDB, pp. 120-131 (2004)
8. Montazerian, M., Wood, P.T., Mousavi, S.R.: Xpath query satisfiability is in ptime
for real-world dtds. In: Barbosa, D., Bonifati, A., Bellahsene, Z., Hunt, E., Unland,
R. (eds.) XSym 2007. LNCS, vol. 4704, pp. 17-30. Springer, Heidelberg (2007)
9. Suzuki, N.: An algorithm for inferring k optimum transformations of xml document
from update script to dtd. IEICE Trans. Inf. & Syst. E93-D(8), 2198-2212 (2010)
10. Suzuki, N., Fukushima, Y.: Satisfiability of simple xpath fragments in the presence
of dtds. In: Proc. WIDM, pp. 15-22 (2009)
