zbMATH — the first resource for mathematics

Integrity constraints for XML. (English) Zbl 1026.68038
Summary: Integrity constraints have proved fundamentally important in database management. The ID/IDREF mechanism provided by XML DTDs relies on a simple form of constraints to describe references. Yet, this mechanism is sufficient neither for specifying references in XML documents, nor for expressing semantic constraints commonly found in databases. In this paper, we extend XML DTDs with several classes of integrity constraints and investigate the complexity of reasoning about these constraints. The constraints range over keys, foreign keys, inverse constraints as well as ID constraints for capturing the semantics of object identities. They improve semantic specifications and provide a better reference mechanism for native XML applications. They are also useful in information exchange and data integration for preserving the semantics of data originating in relational and object-oriented databases. We establish complexity and axiomatization results for the (finite) implication problems associated with these constraints. In addition, we study implication of more general constraints, such as functional, inclusion and inverse constraints defined in terms of navigation paths.

68P15 Database theory
Full Text: DOI
[1] Abiteboul, S.; Cluet, S.; Milo, T.; Mogilevsky, P.; Siméon S. Zohar, J., Tools for data translation and integration, IEEE data eng. bull., 22, 1, 3-8, (1999)
[2] Abiteboul, S.; Hull, R.; Vianu, V., Foundations of databases, (1995), Addison-Wesley Reading, MA
[3] S. Abiteboul, P.C. Kanellakis, Object identity as a query language primitive, in: Proceedings of ACM SIGMOD Conference on Management of Data, Portland, Oregon, June 1989, pp. 159-173. · Zbl 1065.68522
[4] Abiteboul, S.; Vianu, V., Regular path queries with constraints, J. comput. system sci. (JCSS), 58, 4, 429-452, (1999) · Zbl 0939.68025
[5] Barwise, J., On moschovakis closure ordinals, J. symbolic logic, 42, 292-296, (1977) · Zbl 0367.02021
[6] C. Beeri, T. Milo, Schemas for integration and translation of structured and semi-structured data, in: Proceedings of International Conference on Database Theory (ICDT), Jerusalem, Israel, January 1999, pp. 296-313.
[7] Börger, E.; Grädel, E.; Gurevich, Y., The classical decision problem, (1997), Springer Berlin · Zbl 0865.03004
[8] Borgida, A., On the relative expressiveness of description logics and predicate logics, Artif. intell., 82, 1-2, 353-367, (1996)
[9] T. Bray, J. Paoli, C.M. Sperberg-McQueen, Extensible Markup Language (XML) 1.0, W3C Recommendation, February 1998, .
[10] Buneman, P.; Davidson, S.; Fan, W.; Hara, C.; Tan, W., Keys for XML, Comput. networks, 39, 5, 473-487, (2002)
[11] P. Buneman, S. Davidson, W. Fan, C. Hara, W. Tan, Reasoning about keys for XML, in: Proceedings of International Workshop on Database Programming Languages (DBPL), Frascati, Italy, Sept., 2001, Lecture Notes in Computer Science, Vol., 2397, Springer-Verlag, Berlin/New York, 2001, pp. 133-148. · Zbl 1098.68552
[12] P. Buneman, W. Fan, S. Weinstein, Interaction between path and type constraints, in: Proceedings of ACM Symposium on Principles of Database Systems (PODS), Philadelphia, Pennsylvania, May, 1999, pp. 56-67. · Zbl 1365.68197
[13] Buneman, P.; Fan, W.; Weinstein, S., Path constraints in semistructured databases, J. comput. system sci. (JCSS), 61, 2, 146-193, (2000) · Zbl 0963.68056
[14] Calvanese, D.; De Giacomo, G.; Lenzerini, M., Representing and reasoning on XML documentsa description logic approach, J. logic and computat., 9, 3, 295-318, (1999) · Zbl 0938.68842
[15] Cattell, R.G., The object database standard: ODMG 2.0, (1997), Morgan Kaufmann Los Altos, CA · Zbl 0873.68050
[16] J. Clarke, XSL transformations (XSLT), W3C Recommendation, November 1999, .
[17] J. Clark, S. DeRose, XML Path Language (XPath), W3C Working Draft, November 1999, .
[18] S. Cluet, C. Delobel, J. Siméon, K. Smaga, Your mediators need data conversion, in: Proceedings of ACM SIGMOD Conference on Management of Data, Seattle, Washington, June, 1998, pp. 177-188.
[19] S. Cluet, J. Siméon, YATL: a functional and declarative language for XML, Draft manuscript, March, 2000.
[20] Cosmadakis, S.; Kanellakis, P.C.; Vardi, M.Y., Polynomial-time implication problems for unary inclusion dependencies, J. ACM, 37, 1, 15-46, (1990) · Zbl 0698.68090
[21] A. Davidson, M. Fuchs, M. Hedin, M. Jain, J. Koistinen, C. Lloyd, M. Maloney, K. Schwarzhof, Schema for object-oriented XML 2.0, W3C Note, July, 1999, .
[22] A. Deutsch, M.F. Fernandez, D. Florescu, A.Y. Levy, D. Suciu, XML-QL: a query language for XML, W3C Note, August, 1998, .
[23] A. Deutsch, L. Popa, V. Tannen, Physical data independence, constraints, and optimization with universal plans, in: Proceedings of International Conference on Very Large Databases (VLDB), Edinburgh, Scotland, September 1999, pp. 459-470.
[24] W. Fan, L. Libkin, On XML integrity constraints in the presence of DTDs, in: Proceedings of ACM Symposium on Principles of Database Systems (PODS), Santa Barbara, California, May 2001, pp. 114-125. · Zbl 1326.68120
[25] M.F. Fernandez, J. Siméon, P. Wadler, A semi-monad for semi-structured data, in: Proceedings of International Conference on Database Theory (ICDT), London, UK, January 2001, pp. 263-300. · Zbl 1047.68571
[26] Florescu, D.; Raschid, L.; Valduriez, P., A methodology for query reformulation in CIS using semantic knowledge, Internat. J. cooperative inform. systems (IJCIS), 5, 4, 431-468, (1996)
[27] Grädel, E.; Kolaitis, P.G.; Vardi, M.Y., On the decision problem for two-variable first-order logic, Bull. symbolic logic, 3, 1, 53-69, (1997) · Zbl 0873.03009
[28] C. Hara, S. Davidson, Reasoning about nested functional dependencies, in: Proceedings of ACM Symposium on Principles of Database Systems (PODS) Philadephia, Pennsylvania, May 1999, pp. 91-100.
[29] Ito, M.; Weddell, G.E., Implication problems for functional constraints on databases supporting complex objects, J. comput. system sci. (JCSS), 50, 1, 165-187, (1995) · Zbl 0968.68511
[30] O. Lassila, R.R. Swick, Resource Description Framework (RDF) model and syntax specification, W3C Recommendation, February 1999, .
[31] A. Layman, E. Jung, E. Maler, H.S. Thompson, J. Paoli, J. Tigue, N.H. Mikula, S. De Rose, XML-Data, W3C Note, January 1998, .
[32] F. Neven, Extensions of attribute grammars for structured document queries, in: Proceedings of International Workshop on Database Programming Languages (DBPL), Kinloch Rannoch, UK, 1999, Lecture Notes in Computer Science, Vol. 1949, Springer-Verlag, Berlin/New York, pp. 99-116. · Zbl 1044.68045
[33] L. Popa, Object/Relational Query Optimization with Chase and Backchase, PhD Thesis, University of Pennsylvania, 2000.
[34] J. Robie, J. Lapp, D. Schach, XML Query Language (XQL), Workshop on XML Query Languages, 1998.
[35] H.S. Thompson, D. Beech, M. Maloney, N. Mendelsohn, XML Schema, W3C Working Draft, May 2001, .
[36] Ullman, J.D., Database and knowledge base systems, (1988), Computer Science Press Rockville, MD
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.