On Inferences of Weak Multivalued Dependencies

• Autorzy: Hartmann S. , Link S.
• Języki publikacji: EN

Abstrakty

EN

Nesting is a useful technique in many areas of database practice. For instance, nesting is a fundamental operation for the nested relational data model, it can be applied to reduce the level of data redundancy in a database instance, to improve query processing or to convert data from one model to another. We further address the question when nesting operations commute with one another, i.e., when the final nested database relation is independent of the order in which the nesting operations are applied. In fact, it has been shown that the satisfaction of weakmultivalued dependencies provides a sufficient and necessary condition for the commutativity of nesting operations. We study inference systems for different notions of implication for weak multivalued dependencies. First, we establish an axiomatisation with the property that every weak multivalued dependency can be inferred either without any application of the complementation rule or by a single application of the complementation rule necessary only in the very last step of the inference. Consequently, the complementation rule is a mere means to achieve a decomposition of the database. Secondly, we drop the assumption of having a fixed underlying schema, and establish an axiomatisation of weak multivalued dependencies for the notion of implication in this context.

Słowa kluczowe

EN

logic in databases; nested relation; Weak Multivalued Dependency; inference system

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2009
• Tom: Vol. 92, nr 1-2
• Strony: 83--102
• Opis fizyczny: Bibliogr. 42 poz., tab.

Twórcy

autor

Hartmann S.

autor

Link S.

• School of Information Management, Victoria University Wellington, New Zealand,

Bibliografia

• [1] Arenas, M., Libkin, L.: A Normal Form for XML Documents, ACM Trans. Database Syst., 29(1), 2004, 195-232.
• [2] Beeri, C., Fagin, R., Howard, J. H.: A Complete Axiomatization for Functional and Multivalued Dependencies in Database Relations, SIGMOD Conference, ACM, 1977.
• [3] Biskup, J.: Inferences of multivalued dependencies in fixed and undetermined universes, Theor. Comput. Sci., 10(1), 1980, 93-106.
• [4] Biskup, J., Link, S.: Appropriate Reasoning about Data Dependencies in Fixed and Undetermined Universes, FoIKS Conference, 4932, Springer, 2008.
• [5] Buneman, P., Davidson, S., Fan, W., Hara, C., Tan, W.: Reasoning about keys for XML, Inf. Syst., 28(8), 2003, 1037-1063.
• [6] Butz, C., Sanscartier, M.: Properties of Weak Conditional Independence, Rough Sets and Current Trends in Computing Conference, 2475, Springer, 2002.
• [7] Codd, E. F.: A relational model of data for large shared data banks, Commun. ACM, 13(6), 1970, 377-387.
• [8] Fagin, R.: Multivalued Dependencies and a New Normal Form for Relational Databases, ACM Trans. Database Syst., 2(3), 1977, 262-278.
• [9] Fischer, P., Saxton, L. V., Thomas, S. J., Van Gucht, D.: Interactions between Dependencies and Nested Relational Structures, J. Comput. Syst. Sci., 31(3), 1985, 343-354.
• [10] Fischer, P., Van Gucht, D.: Weak Multivalued Dependencies, PoDS Conference, ACM, 1984.
• [11] van Gucht, D.: Theory of unnormalized relational structures, Technical Report CS-85-07, Vanderbilt University, 1985.
• [12] Hartmann, S., Kőhler, H., Link, S.: Full Hierarchical Dependencies in Fixed and Undetermined Universes, Ann. Math. Artif. Intell., 50(1-2), 2007, 195-226.
• [13] Hartmann, S., Link, S.: More Functional Dependencies for XML, ADBIS Conference, number 2798 in Lecture Notes in Computer Science, Springer, 2003.
• [14] Hartmann, S., Link, S.: On a Problem of Fagin concerning Multivalued Dependencies in Relational Databases, Theor. Comput. Sci., 353(1-3), 2006, 53-62.
• [15] Hartmann, S., Link, S.: Characterising nested database dependencies by fragments of propositional logic, Ann. Pure Appl. Logic, 152(1-3), 2007, 84-106.
• [16] Hartmann, S., Link, S.: Efficient Reasoning about a Robust XML Key Fragment, ACM Trans. Database Syst., 34(1:3), 2009.
• [17] Hartmann, S., Trinh, T.: Axiomatising functional dependencies for XML with frequencies, FoIKS Conference, number 3861 in Lecture Notes in Computer Science, Springer, 2006.
• [18] Herrmann, C.: On the Undecidability of Implications Between Embedded Multivalued Database Dependencies, Inf. Comput., 122(2), 1995, 221-235.
• [19] Herrmann, C.: Corrigendum to "On the Undecidability of Implications Between Embedded Multivalued Database Dependencies", Inf. Comput., 204(12), 2006, 1847-1851.
• [20] Jaeschke, G., Schek, H.-J.: Remarks on the Algebra of Non First Normal Form Relations, PoDS Conference, 1982.
• [21] Kambayashi, Y., Yoshikawa, M.: Query Processing utilizing dependencies and horizontal decomposition, SIGMOD Conference, 1983.
• [22] Kitagawa, H., Kunii, T., Ohbo, N.: Classification of nested tables under deeply nested algebra, System Sciences Conference, 1991.
• [23] Koller, D., Pfeffer, A.: Object-oriented Bayesian Networks, UAI Conference, Morgan Kaufmann, 1997.
• [24] Korth, H., Roth, M.: Query languages for Nested Relational Databases, Nested Relations and Complex Objects in Databases, 361, Springer, 1991.
• [25] Lee, D., Mani, M., Chiu, F., Chu, W.: NeT & CoT: translating relational schemas to XML schemas using semantic constraints, CIKM Conference, 2002.
• [26] Levene, M., Loizou, G.: The Nested Universal Relation Data Model, J. Comput. Syst. Sci., 49(3), 1994, 683-717.
• [27] Link, S.: Charting the completeness frontier of inference systems for multivalued dependencies, Acta Inf., 45(7-8), 2008, 565-591.
• [28] Link, S.: On the Implication of Multivalued Dependencies in Partial Database Relations, Int. J. Found. Comput. Sci., 19(3), 2008, 691-715.
• [29] Makinouchi, A.: A Consideration on Normal Form of Not-Necessarily-Normalised Relation in the Relational Data Model, VLDB Conference, IEEE Computer Society, 1977.
• [30] Paredaens, J., De Bra, P., Gyssens, M., Van Gucht, D.: The Structure of the Relational Database Model, Springer, 1989.
• [31] Pearl, J.: Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference, Morgan-Kaufmann, 1988.
• [32] Saxton, L., Raghavan, V.: Design of an Integrated Information Retrieval/Database Management System, IEEE Trans. Knowl. Data Eng., 2(2), 1990, 210-219.
• [33] Saxton, L., Tang, X.: Tree Multivalued Dependencies for XML Datasets, WAIM Conference, number 3129 in Lecture Notes in Computer Science, Springer, 2004.
• [34] Schek, H.-J., Scholl, M.: The relational model with relation-valued attributes, Inf. Syst., 11(2), 1986, 137-147.
• [35] Thalheim, B.: Entity-Relationship Modeling: Foundations of Database Technology, Springer, 2000.
• [36] Thalheim, B.: Conceptual Treatment of Multivalued Dependencies, Conceptual Modeling Conference, number 2813 in Lecture Notes in Computer Science, Springer, 2003.
• [37] Thomas, S.: A Non-First-Normal-Form Relational Database Model, Ph.D. Thesis, Vanderbilt University, 1983.
• [38] Vincent, M., Liu, J., Liu, C.: A redundancy free 4NF for XML, XSym Conference, number 2824 in Lecture Notes in Computer Science, Springer, 2003.
• [39] Vincent, M., Liu, J., Liu, C.: Strong Functional Dependencies and their Application to Normal Forms in XML, ACM Trans. Database Syst., 29(3), 2004, 445-462.
• [40] Vincent, M., Liu, J., Mohania, M.: On the equivalence between FDs in XML and FDs in relations, Acta Inf., 44(3-4), 2007, 207-247.
• [41] Wong, S., Butz, C., Wu, D.: On the Implication Problem for Probabilistic Conditional Independency, IEEE Transactions on Systems, Man, and Cybernetics, Part A: Systems and Humans, 30(6), 2000, 785-805.
• [42] Zaniolo, C., Melkanoff, M.: On the Design of Relational Database Schemata, ACM Trans. Database Syst., 6(1), 1981, 1-47.