Abstract
Inclusion between XML types is important but expensive, and is much more expensive when unordered types are considered. We prove here that inclusion for XML types with interleaving and counting can be decided in polynomial time in presence of two important restrictions: no element appears twice in the same content model, and Kleene star is only applied to disjunctions of single elements.
Our approach is based on the transformation of each such type into a set of constraints that completely characterizes the type. We then provide a complete deduction system to verify whether the constraints of one type imply all the constraints of another one.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Gelade, W., Martens, W., Neven, F.: Optimizing schema languages for XML: Numerical constraints and interleaving. In: Schwentick, T., Suciu, D. (eds.) ICDT 2007. LNCS, vol. 4353, Springer, Heidelberg (2006)
Mayer, A.J., Stockmeyer, L.J.: Word problems-this time with interleaving. Inf. Comput. 115, 293–311 (1994)
Bex, G.J., Neven, F., den Bussche, J.V.: DTDs versus XML schema: A practical study. In: Amer-Yahia, S., Gravano, L. (eds.) WebDB, pp. 79–84 (2004)
Bex, G.J., Neven, F., Schwentick, T., Tuyls, K.: Inference of concise DTDs from XML data. In: Dayal, U., Whang, K.Y., Lomet, D.B., Alonso, G., Lohman, G.M., Kersten, M.L., Cha, S.K., Kim, Y.K. (eds.) VLDB, pp. 115–126. ACM Press, New York (2006)
Amer-Yahia, S., Cho, S., Lakshmanan, L.V.S., Srivastava, D.: Minimization of tree pattern queries. In: SIGMOD Conference, pp. 497–508 (2001)
Thompson, H.S., Beech, D., Maloney, M., Mendelsohn, N.: XML Schema Part 1: Structures Second Edition. Technical report, World Wide Web Consortium, W3C Recommendation (2004)
Martens, W., Neven, F., Schwentick, T.: Complexity of decision problems for simple regular expressions. In: Fiala, J., Koubek, V., Kratochvíl, J. (eds.) MFCS 2004. LNCS, vol. 3153, pp. 889–900. Springer, Heidelberg (2004)
Wood, P.T.: Containment for XPath fragments under DTD constraints. In: Calvanese, D., Lenzerini, M., Motwani, R. (eds.) ICDT 2003. LNCS, vol. 2572, pp. 300–314. Springer, Heidelberg (2002)
Ghelli, G., Colazzo, D., Sartiani, C.: Efficient inclusion for a class of XML types with interleaving and counting. Technical report, Dipartimento di Informatica - Università di Pisa (2007)
Beeri, C., Bernstein, P.A.: Computational problems related to the design of normal form relational schemas. ACM Trans. Database Syst. 4, 30–59 (1979)
Bender, M.A., Farach-Colton, M.: The LCA problem revisited. In: Gonnet, G.H., Viola, A. (eds.) LATIN 2000. LNCS, vol. 1776, pp. 88–94. Springer, Heidelberg (2000)
Foster, J.N., Pierce, B.C., Schmitt, A.: A logic your typechecker can count on: Unordered tree types in practice. In: PLAN-X, informal proceedings (2007)
Barbosa, D., Mendelzon, A.O., Libkin, L., Mignet, L., Arenas, M.: Efficient incremental validation of XML documents. In: ICDE, pp. 671–682. IEEE Computer Society Press, Los Alamitos (2004)
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 2007 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Ghelli, G., Colazzo, D., Sartiani, C. (2007). Efficient Inclusion for a Class of XML Types with Interleaving and Counting. In: Arenas, M., Schwartzbach, M.I. (eds) Database Programming Languages. DBPL 2007. Lecture Notes in Computer Science, vol 4797. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-75987-4_16
Download citation
DOI: https://doi.org/10.1007/978-3-540-75987-4_16
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-75986-7
Online ISBN: 978-3-540-75987-4
eBook Packages: Computer ScienceComputer Science (R0)