Counter-Free Keys and Functional Dependencies in Higher-Order Datamodels

• Autorzy: Sali A. , Schewe K-D.
• Języki publikacji: EN

Abstrakty

EN

We investigate functional dependencies (FDs) in the presence of several constructors for complex values. These constructors are the tuple constructor, list-, set- and multiset-constructors, an optionality constructor, and a disjoint union constructor. The disjoint union constructor implies restructuring rules, which complicate the theory. In particular, they do not permit a straightforward axiomatisation of the class of all FDs without a detour via weak functional dependencies (wFDs), i.e. disjunctions of functional dependencies, and even the axiomatisation of wFDs is not yet completely solved. Therefore, we look at the restricted class of counter-free functional dependencies (cfFDs). That is, we ignore subattributes that only refer to counting the number of elements in sets or multisets or distinguish only between empty or non-empty sets. We present a finite axiomatisation for the class of cfFDs. Furthermore, we study keys ignoring again the counting subattributes. We show that such keys are equivalent with certain ideals called HL-ideals. Based on that we introduce an ordering between key sets, and investigate systems of minimal keys. We give a sufficient condition for a Sperner family of HL-ideals being a system of minimal keys, and determine lower and upper bounds for the size of the smallest Armstrong-instance.

Słowa kluczowe

EN

functional dependencies; keys; type constructors; axiomatization; Sperner families

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2006
• Tom: Vol. 70, nr 3
• Strony: 277--301
• Opis fizyczny: bibliogr. 27 poz.

Twórcy

autor

Sali A.

autor

Schewe K-D.

• Alfred Rényi Institute of Mathematics, Hungarian Academy of Sciences, Budapest, P.O.B. 127, H-1364 Hungary,

Bibliografia

• [1] Abiteboul, S., Buneman, P., Suciu, D.: Data on the Web: From Relations to Semistructured Data and XML, Morgan Kaufmann Publishers, 2000.
• [2] Abiteboul, S., Hull, R.: Restructuring Hierarchical Database Objects, Theoretical Computer Science, 62(1-2), 1988, 3-38.
• [3] Abiteboul, S., Hull, R., Vianu, V.: Foundations of Databases, Addison-Wesley, 1995.
• [4] Arenas, M., Libkin, L.: A Normal Form for XML Documents, PODS 2002, ACM, 2002.
• [5] Armstrong, W. W.: Dependency structures of database relationships, Information Processing, 1974, 580-583.
• [6] Brightwell, G., Katona, G.: A new type of coding theorem, Studia ScientiarumMathematicarum Hungarica, 38, 2001, 139-147.
• [7] Buneman, P., Davidson, S., Fan, W., Hara, C., Tan, W.: Keys for XML, Tenth WWW Conference, IEEE, 2001.
• [8] Demetrovics, J.: On the equivalence of candidate keys with Sperner systems, Acta Cybernetica, 4, 1979, 247-252.
• [9] Demetrovics, J., Katona, G.: Extremal combinatorial problems in relational data base, in: Fundamentals of Computing Theory (FCT 1981), number 117 in LNCS, Springer-Verlag, Berlin, 1981, 110-119.
• [10] Demetrovics, J., Katona, G., Sali, A.: The characterization of branching dependencies, Discrete Applied Mathematics, 40, 1992, 139-153.
• [11] Demetrovics, J., Katona, G., Sali, A.: Design type problems motivated by database theory, Journal of Statistical Planning and Inference, 72, 1998, 149-164.
• [12] Ganter, B., Gronau, H.-D. O. F., Mullin, R. C.: On orthogonal double covers of Kn, Ars Combinatoria, 37, 1994, 209-221.
• [13] Hartmann, S., Hoffmann, A., Link, S., Schewe, K.-D.: Axiomatizing Functional Dependencies in the Higher-Order Entity Relationship Model, Information Processing Letters, 87(3), 2003, 133-137.
• [14] Hartmann, S., Link, S.: Reasoning about functional dependencies in an abstract data model, Electronic Notes in Theoretical Computer Science, 84, 2003.
• [15] Hartmann, S., Link, S., Schewe, K.-D.: Axiomatisation of Functional Dependencies in the Presence of Records, Lists, Sets and Multisets, Technical Report 1/2004, Massey University, Department of Information Systems, 2004, Available from http://infosys.massey.ac.nz/research/rs techreports.html.
• [16] Hartmann, S., Link, S., Schewe, K.-D.: Reasoning about Functional and Multi-Valued Dependencies in the Presence of Lists, Foundations of Information and Knowledge Systems (D. Seipel, J. M. Turull Torres, Eds.), 2942, Springer Verlag, 2004.
• [17] Hartmann, S., Link, S., Schewe, K.-D.: Weak Functional Dependencies in Higher-Order Datamodels, Foundations of Information and Knowledge Systems (D. Seipel, J. M. Turull Torres, Eds.), 2942, Springer Verlag, 2004.
• [18] Mok, W. Y., Ng, Y. K., Embley, D. W.: A normal form for precisely charachterizing redundancy in nested relations, Transactions on Database Systems, 21, 1996, 77-106.
• [19] Özsoyoglu, Z. M., Yuan, L. Y.: A new normal form for nested relations, Transactions on Database Systems, 12, 1987, 111-136.
• [20] Paredaens, J., De Bra, P., Gyssens, M., Van Gucht, D.: The Structure of the Relational Database Model, Springer-Verlag, 1989.
• [21] Sali, A.: Minimal Keys in Higher-Order Datamodels, Foundations of Information and Knowledge Systems (D. Seipel, J. M. Turull Torres, Eds.), 2942, Springer Verlag, 2004.
• [22] Schewe, K.-D., Thalheim, B.: Fundamental Concepts of Object Oriented Databases, Acta Cybernetica, 11(4), 1993, 49-85.
• [23] Thalheim, B.: Dependencies in Relational Databases, Teubner-Verlag, 1991.
• [24] Thalheim, B.: Foundations of Entity-Relationship Modeling, Annals of Mathematics and Artificial Intelligence, 6, 1992, 197-256.
• [25] Thalheim, B.: Entity-Relationship Modeling: Foundations of Database Technology, Springer-Verlag, 2000.
• [26] Vincent, M. W., Liu, J.: Functional Dependencies for XML, Web Technologies and Applications: 5th Asia-Pacific Web Conference, 2642, Springer-Verlag, 2003.
• [27] Vincent, M. W., Liu, J.: Multivalued Dependencies in XML, British National Conference on Database Systems: BNCOD 2003, 2712, Springer-Verlag, 2003.