Efficient reasoning about a robust XML key fragment

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Efficient reasoning about a robust XML key fragment

Full text

Pdf (767 KB)

Source

ACM Transactions on Database Systems (TODS) archive
Volume 34 , Issue 2 (June 2009) table of contents

Article No. 10

Year of Publication: 2009

ISSN:0362-5915

Authors

Sven Hartmann	Clausthal University of Technology, Clausthal-Zellerfeld, Germany
Sebastian Link	Victoria University of Wellington, Wellington, New Zealand

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 27, Downloads (12 Months): 121, Citation Count: 0

Additional Information:

abstract references index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/1538909.1538912 What is a DOI?

ABSTRACT

We review key constraints in the context of XML as introduced by Buneman et al. We demonstrate that:

(1) one of the proposed inference rules is not sound in general, and

(2) the inference rules are incomplete for XML key implication, even for nonempty sets of simple key paths.

This shows, in contrast to earlier statements, that the axiomatizability of XML keys is still open, and efficient algorithms for deciding their implication still need to be developed. Solutions to these problems have a wide range of applications including consistency validation, XML schema design, data exchange and integration, consistent query answering, XML query optimization and rewriting, and indexing.

In this article, we investigate the axiomatizability and implication problem for XML keys with nonempty sets of simple key paths. In particular, we propose a set of inference rules that is indeed sound and complete for the implication of such XML keys. We demonstrate that this fragment is robust by showing the duality of XML key implication to the reachability problem of fixed nodes in a suitable digraph. This enables us to develop a quadratic-time algorithm for deciding implication, and shows that reasoning about this XML key fragment is practically efficient. Therefore, XML applications can be unlocked effectively since they benefit not only from those XML keys specified explicitly by the data designer but also from those that are specified implicitly.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Serge Abiteboul , Richard Hull , Victor Vianu, Foundations of Databases: The Logical Level, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1995
	2	Apparao, V. 1998. Document object model (DOM) level 1 specification, W3C recommendation. http://www.w3.org/TR/REC-DOM-Level-1/.
	3	Marcelo Arenas , Leonid Libkin, A normal form for XML documents, ACM Transactions on Database Systems (TODS), v.29 n.1, p.195-232, March 2004 [doi>10.1145/974750.974757]
	4	Marcelo Arenas , Leonid Libkin, An information-theoretic approach to normal forms for relational and XML data, Journal of the ACM (JACM), v.52 n.2, p.246-283, March 2005 [doi>10.1145/1059513.1059519]
	5	Michael Benedikt , Wenfei Fan , Gabriel Kuper, Structural properties of XPath fragments, Theoretical Computer Science, v.336 n.1, p.3-31, 25 May 2005 [doi>10.1016/j.tcs.2004.10.030]
	6	Joachim Biskup , Torsten Polle, Decomposition of object-oriented database schemas, Annals of Mathematics and Artificial Intelligence, v.33 n.2-4, p.119-155, December 2001 [doi>10.1023/A:1013134906161]
	7	Bray, T., Paoli, J., Sperberg-McQueen, C. M., Maler, E., and Yergeau, F. 2006. Extensible markup language (XML) 1.0 (fourth edition) W3C recommendation. http://www.w3.org/TR/xml.
	8	Peter Buneman , Susan B. Davidson , Wenfei Fan , Carmem S. Hara , Wang Chiew Tan, Reasoning about Keys for XML, Revised Papers from the 8th International Workshop on Database Programming Languages, p.133-148, September 08-10, 2001
	9	Buneman, P., Davidson, S., Fan, W., Hara, C., and Tan, W. 2002. Keys for XML. Comput. Netw. 39, 5, 473--487.
	10	Peter Buneman , Susan Davidson , Wenfei Fan , Carmem Hara , Wang-Chiew Tan, Reasoning about keys for XML, Information Systems, v.28 n.8, p.1037-1063, December 2003 [doi>10.1016/S0306-4379(03)00028-0]
	11	Peter Buneman , Wenfei Fan , Jérôme Siméon , Scott Weinstein, Constraints for semistructured data and XML, ACM SIGMOD Record, v.30 n.1, p.47-54, March 2001 [doi>10.1145/373626.373697]
	12	Peter Buneman , Wenfei Fan , Scott Weinstein, Path constraints in semistructured databases, Journal of Computer and System Sciences, v.61 n.2, p.146-193, Oct. 2000 [doi>10.1006/jcss.2000.1710]
	13	Chomicki, J. 2007. Consistent query answering: Five easy pieces. In Proceedings of the 11th International Conference on Database Theory (ICDT). Lecture Notes in Computer Science, vol. 4353. Springer, 1--17.
	14	Jan Chomicki , Damian Niwiński, On the feasibility of checking temporal integrity constraints, Journal of Computer and System Sciences, v.51 n.3, p.523-535, Dec. 1995 [doi>10.1006/jcss.1995.1088]
	15	Clark, J. and DeRose, S. 1999. XML path language (XPath) version 1.0, W3C recommendation. http://www.w3.org/TR/xpath.
	16	Susan Davidson , Wenfei Fan , Carmem Hara, Propagating XML constraints to relations, Journal of Computer and System Sciences, v.73 n.3, p.316-361, May, 2007 [doi>10.1016/j.jcss.2006.10.022]
	17	Susan Davidson , Wenfei Fan , Carmem Hara, Erratum: Erratum to “Propagating XML constraints to relations” [J. Comput. System Sci. 73 (2007) 316--361], Journal of Computer and System Sciences, v.74 n.3, p.404-405, May, 2008 [doi>10.1016/j.jcss.2007.09.002]
	18	Alin Deutsch , Val Tannen, XML Queries and constraints, containment and reformulation, Theoretical Computer Science, v.336 n.1, p.57-87, 25 May 2005 [doi>10.1016/j.tcs.2004.10.032]
	19	Ronald Fagin , Moshe Y. Vardi, The Theory of Data Dependencies - An Overview, Proceedings of the 11th Colloquium on Automata, Languages and Programming, p.1-22, July 16-20, 1984
	20	Fan, W. 2005. XML constraints. In Proceedings of the 16th International Workshop on Database and Expert Systems Applications (DEXA'05). IEEE Computer Society, 805--809.
	21	Wenfei Fan , Leonid Libkin, On XML integrity constraints in the presence of DTDs, Journal of the ACM (JACM), v.49 n.3, p.368-406, May 2002 [doi>10.1145/567112.567117]
	22	Wenfei Fan , Jérôme Siméon, Integrity constraints for XML, Journal of Computer and System Sciences, v.66 n.1, p.254-291, 01 February 2003 [doi>10.1016/S0022-0000(02)00032-6]
	23	Georg Gottlob , Christoph Koch , Reinhard Pichler, Efficient algorithms for processing XPath queries, ACM Transactions on Database Systems (TODS), v.30 n.2, p.444-491, June 2005 [doi>10.1145/1071610.1071614]
	24	Carmem S. Hara , Susan B. Davidson, Reasoning about nested functional dependencies, Proceedings of the eighteenth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.91-100, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States [doi>10.1145/303976.303985]
	25	Sven Hartmann, On the implication problem for cardinality constraints and functional dependencies, Annals of Mathematics and Artificial Intelligence, v.33 n.2-4, p.253-307, December 2001 [doi>10.1023/A:1013133428451]
	26	Hartmann, S., Koehler, H., Link, S., Trinh, T., and Wang, J. 2007. On the notion of an XML key. In Proceedings of the 3rd International Workshop on Semantics in Data and Knowledge Bases (SDKB). Lecture Notes in Computer Science, vol. 4925. Springer, 103--112.
	27	Hartmann, S. and Link, S. 2007a. Numerical constraints for XML. In Proceedings of the 14th International Workshop on Logic, Language, Information and Computation (WoLLIC). Lecture Notes in Computer Science, vol. 4576. Springer, 203--217.
	28	Hartmann, S. and Link, S. 2007b. Unlocking keys for XML trees. In Proceedings of the 11th International Conference on Database Theory (ICDT). Lecture Notes in Computer Science, vol. 4353. Springer, 104--118.
	29	Hartmann, S. and Link, S. 2008. Characterising nested database dependencies by fragments of propositional logic. Ann. Pure Appl. Logic 152, 1-3, 84--106.
	30	Hartmann, S. and Trinh, T. 2006. Axiomatising functional dependencies for XML with frequencies. In Proceedings of the 4th International Symposium on Foundations of Information and Knowledge Systems (FoIKS'06). Lecture Notes in Computer Science, vol. 3861. Springer, 159--178.
	31	Minoru Ito , Grant E. Weddell, Implication problems for functional constraints on databases supporting complex objects, Journal of Computer and System Sciences, v.49 n.3, p.726-768, Dec. 1994
	32	Christian S. Jensen , Richard Thomas Snodgrass , Michael D. Soo, Extending Existing Dependency Theory to Temporal Databases, IEEE Transactions on Knowledge and Data Engineering, v.8 n.4, p.563-582, August 1996 [doi>10.1109/69.536250]
	33	Dieter Jungnickel, Graphs, Networks and Algorithms, Springer Publishing Company, Incorporated, 2007
	34	Maurizio Lenzerini , Paolo Nobili, On the satisfiability of dependency constraints in entity-relationship schemata, Information Systems, v.15 n.4, p.453-461, 1990 [doi>10.1016/0306-4379(90)90048-T]
	35	Stephen W. Liddle , David W. Embley , Scott N. Woodfield, Cardinality constraints in semantic data models, Data & Knowledge Engineering, v.11 n.3, p.235-270, Dec. 1993 [doi>10.1016/0169-023X(93)90024-J]
	36	Gerome Miklau , Dan Suciu, Containment and equivalence for a fragment of XPath, Journal of the ACM (JACM), v.51 n.1, p.2-45, January 2004 [doi>10.1145/962446.962448]
	37	Neven, F. and Schwentick, T. 2006. On the complexity of XPath containment in the presence of disjunction, DTDs, and variables. Logical Methods Comput. Sci. 2, 3:1.
	38	Jan Paredaens , Paul De Bra , Marc Gyssens , Dirk Van Gucht, The structure of the relational database model, Springer-Verlag New York, Inc., New York, NY, 1989
	39	Dan Suciu, On database theory and XML, ACM SIGMOD Record, v.30 n.3, September 2001 [doi>10.1145/603867.603874]
	40	Zahir Tari , John Stokes , Stefano Spaccapietra, Object normal forms and dependency constraints for object-oriented schemata, ACM Transactions on Database Systems (TODS), v.22 n.4, p.513-569, Dec. 1997 [doi>10.1145/278245.278247]
	41	Thalheim, B. 1991. Dependencies in Relational Databases. Teubner.
	42	Thalheim, B. 2000. Entity-Relationship Modelling. Springer.
	43	Thompson, H., Beech, D., Maloney, M., and Mendelsohn, N. 2004. XML schema part 1: Structures 2nd Ed. W3C recommendation. http://www.w3.org/TR/xmlschema-1/.
	44	Victor Vianu, A Web odyssey: from codd to XML, ACM SIGMOD Record, v.32 n.2, June 2003 [doi>10.1145/776985.776999]
	45	Millist W. Vincent , Jixue Liu , Chengfei Liu, Strong functional dependencies and their application to normal forms in XML, ACM Transactions on Database Systems (TODS), v.29 n.3, p.445-462, September 2004 [doi>10.1145/1016028.1016029]
	46	Millist W. Vincent , Jixue Liu , Mukesh Mohania, On the equivalence between FDs in XML and FDs in relations, Acta Informatica, v.44 n.3, p.207-247, June 2007 [doi>10.1007/s00236-007-0048-x]
	47	Grant E. Weddell, Reasoning about functional dependencies generalized for semantic data models, ACM Transactions on Database Systems (TODS), v.17 n.1, p.32-64, March 1992 [doi>10.1145/128765.128767]
	48	Widom, J. 1999. Data management for XML: Research directions. Data Engin. Bull. 22, 3, 44--52.
	49	Peter T. Wood, Containment for XPath Fragments under DTD Constraints, Proceedings of the 9th International Conference on Database Theory, p.300-314, January 08-10, 2003