Expressive, yet tractable XML keys

ABSTRACT

Constraints are important for a variety of XML recommendations and applications. Consequently, there are numerous opportunities for advancing the treatment of XML semantics. In particular, suitable notions of keys will enhance XML's capabilities of modeling, managing and processing native XML data. However, the different ways of accessing and comparing XML elements make it challenging to balance expressiveness and tractability.

We investigate XML keys which uniquely identify XML elements based on a very general notion of value-equality: isomorphic subtrees with the identity on data values. Previously, an XML key fragment has been recognised that is robust in the sense that its implication problem can be expressed as the reachability problem in a suitable digraph. We analyse the impact of extending this fragment by structural keys that uniquely identify XML elements independently of any data. We establish a sound and complete set of inference rules for this expressive fragment of XML keys, and encode these rules in an algorithm that decides the associated implication problem in time quadratic in the size of the input keys. Consequently, we gain significant expressiveness without any loss of efficiency in comparison to less expressive XML key fragments.

REFERENCES

• 1: Serge Abiteboul , Richard Hull , Victor Vianu, Foundations of Databases: The Logical Level, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1995
• 2: V. Apparao et al. Document object model (DOM) Level 1 Specification, W3C Recommendation, Oct. 1998. http://www.w3.org/TR/REC-DOM-Level-1/.
• 3: Marcelo Arenas , Wenfei Fan , Leonid Libkin, What's Hard about XML Schema Constraints?, Proceedings of the 13th International Conference on Database and Expert Systems Applications, p.269-278, September 02-06, 2002
• 4: 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]
• 5: 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]
• 6: 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]
• 7: T. Bray, J. Paoli, C. M. Sperberg-McQueen, E. Maler, and F. Yergeau. Extensible markup language (XML) 1.0 (Fourth Edition) W3C Recommendation, Aug. 2006. http://www.w3.org/TR/xml/.
• 8: P. Buneman, S. Davidson, W. Fan, C. Hara, and W. Tan. Keys for XML. Computer Networks, 39(5):473--487, 2002.
• 9: 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]
• 10: 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]
• 11: 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]
• 12: 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]
• 13: 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]
• 14: 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]
• 15: W. Fan. XML constraints. In DEXA Workshops, pages 805--809, 2005.
• 16: 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]
• 17: 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]
• 18: S. Hartmann, H. Köhler, S. Link, T. Trinh, and J. Wang. On the notion of an XML key. In Proceedings of the 3rd International Workshop on Semantics in Data and Knowledge Bases - SDKB 2008, number 4925 in Lecture Notes in Computer Science, pages 114--123. Springer, 2007.
• 19: S. Hartmann and S. Link Characterising nested database dependencies by fragments of propositional logic. Ann. Pure Appl. Logic, 152(1--3):84--106, 2008.
• 20: S. Hartmann and S. Link. Numerical constraints for XML. In Proceedings of the 14th International Workshop on Logic, Language, Information and Computation - WoLLIC 2007, number 4576 in Lecture Notes in Computer Science, pages 203--217. Springer, 2007.
• 21: S. Hartmann and S. Link. Unlocking keys for XML trees. In Proceedings of the 11th International Conference on Database Theory - ICDT 2007, number 4353 in Lecture Notes in Computer Science, pages 104--118. Springer, 2007.
• 22: S. Hartmann and T. Trinh. Axiomatising functional dependencies for XML with frequencies. In Proceedings of the 4th International Symposium on Foundations of Information and Knowledge Systems - FolKS 2006, number 3861 in Lecture Notes in Computer Science, pages 159--178. Springer, 2006.
• 23: D. Jungnickel. Graphs, Networks and Algorithms. Springer, 1999.
• 24: J. Clark and S. DeRose. XML Path Language (XPath) Version 1.0 W3C Recommendation Nov. 1999. http://www.w3.org/TR/xpath.
• 25: S. Link. On the Implication of Multivalued Dependencies in Partial Database Relations. Int. J. Found. Comput. Sci., 19(3):691--715, 2008.
• 26: Sebastian Link, Charting the completeness frontier of inference systems for multivalued dependencies, Acta Informatica, v.45 n.7-8, p.565-591, November 2008 [doi>10.1007/s00236-008-0080-5]
• 27: 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]
• 28: F. Neven and T. Schwentick. On the complexity of XPath containment in the presence of disjunction, DTDs, and variables. Logical Methods in Computer Science, 2(3), 2006.
• 29: S. e. a. Pemberton. XHTML 1.0 The Extensible HyperText Markup Language (Second Edition) W3C Recommendation, Jan. 2000. http://www.w3.org/TR/xhtml1.
• 30: L. V. Saxton and X. Tang. Tree Multivalued Dependencies for XML Datasets. In Proceedings of the 5th International Conference on Advances in Web-Age Information Management - WAIM 2004, number 3129 in Lecture Notes in Computer Science, pages 357--367. Springer, 2004.
• 31: Dan Suciu, On database theory and XML, ACM SIGMOD Record, v.30 n.3, September 2001 [doi>10.1145/603867.603874]
• 32: H. Thompson, D. Beech, M. Maloney, and N. Mendelsohn. XML Schema Part 1: Structures second edition, W3C Recommendation, Oct. 2004. http://www.w3.org/TR/xmlschema-1/.
• 33: Victor Vianu, A Web odyssey: from codd to XML, ACM SIGMOD Record, v.32 n.2, June 2003 [doi>10.1145/776985.776999]
• 34: M. W. Vincent, J. Liu and C. Liu. A Redundancy Free 4NF for XML. In Proceedings of the First International XML Database Symposium - XSym 2003, number 2824 in Lecture Notes in Computer Science, pages 254--266. Springer, 2003.
• 35: 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]
• 36: 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]
• 37: J. Wang. Using tree patterns for flexible handling of XML trees. Master's thesis, Massey University, 2007.
• 38: 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