On Inferences of Full First-Order Hierarchical Decompositions

Link, S.

Artykuł - szczegóły

Tytuł artykułu

On Inferences of Full First-Order Hierarchical Decompositions

Autorzy

Link S.

Wybrane pełne teksty z tego czasopisma

https://fi.episciences.org/

Identyfikatory

Warianty tytułu

Języki publikacji

Abstrakty

Database design aims to find a database schema that permits the efficient processing of common types of queries and updates on future database instances. Full first-order hierarchical decompositions constitute a large class of database constraints that can provide assistance to the database designer in identifying a suitable database schema. We establish finite axiomatisations of full first-order hierarchical decompositions that mimic best database design practice. That is, an inference engine derives all the independent collections of the universal schema during database normalization, and the designer determines during database denormalization which re-combinations of these independent collections manifest the final database schema. We also show that well-known correspondences between multivalued dependencies, degenerated multivalued dependencies, and a fragment of Boolean propositional logic do not extend beyond binary full first-order hierarchical decompositions.

Słowa kluczowe

relational model of data database decomposition database constraint axiomatisation propositional logic

Wydawca

IOS Press

Czasopismo

Fundamenta Informaticae

Rocznik

2011

Tom

Vol. 106, nr 2-4

Strony

233--258

Opis fizyczny

Bibliogr. 73 poz.

Twórcy

autor

Link S.

School of Information Management, Centre for Logic, Language and Computation, Victoria University, Wellington, New Zealand, sebastian.link@vuw.ac.nz

Bibliografia

[1] S. Abiteboul, R. Hull, and V. Vianu. Foundations of Databases. Addison-Wesley, 1995.
[2] A. Aho, C. Beeri, and J. Ullman. The theory of joins in relational databases. ACM Trans. Database Syst., 4(3):297-314, 1979.
[3] M. Arenas and L. Libkin. A normal form for XML documents. ACM Trans. Database Syst., 29(1):195-232, 2004.
[4] W. W. Armstrong. Dependency structures of database relationships. Information Processing, 74:580-583, 1974.
[5] W. W. Armstrong and C. Delobel. Decomposition and functional dependencies in relations. ACM Trans. Database Syst., 5(4):404-430, 1980.
[6] C. Beeri. On the membership problem for functional and multivalued dependencies in relational databases. ACM Trans. Database Syst., 5(3):241-259, 1980.
[7] C. Beeri and P. A. Bernstein. Computational problems related to the design of normal form relational schemata. ACM Trans. Database Syst., 4(1):30-59, 1979.
[8] C. Beeri, M. Dowd, R. Fagin, and R. Statman. On the structure of Armstrong relations for functional dependencies. J. ACM, 31(1):30-46, 1984.
[9] C. Beeri, R. Fagin, and J. H. Howard. A complete axiomatization for functional andmultivalued dependencies in database relations. In SIGMOD, pages 47-61. ACM, 1977.
[10] P. Bernstein. Synthesizing third normal form relations from functional dependencies. ACM Trans. Database Syst., 1(4):277-298, 1976.
[11] P. A. Bernstein and N. Goodman. What does Boyce-Codd normal form do? In VLDB, pages 245-259. IEEE Computer Society, 1980.
[12] J. Biskup. On the complementation rule for multivalued dependencies in database relations. Acta Inf., 10(3):297-305, 1978.
[13] J. Biskup. Inferences of multivalued dependencies in fixed and undetermined universes. Theor. Comput. Sci., 10(1):93-106, 1980.
[14] J. Biskup and S. Link. Appropriate reasoning about data dependencies in fixed and undetermined universes. In FoIKS, number 4932 in Lecture Notes in Computer Science, pages 58-77, 2008.
[15] T. Bray, J. Paoli, C. M. Sperberg-McQueen, E. Maler, and F. Yergeau. Extensible markup language (XML) 1.0 (fourth edition)W3C recommendation. http://www.w3.org/TR/xml, 2006.
[16] P. Buneman, S. Davidson,W. Fan, C. Hara, andW. Tan. Keys for XML. Computer Networks, 39(5):473-487, 2002.
[17] E. F. Codd. A relational model of data for large shared data banks. Commun. ACM, 13(6):377-387, 1970.
[18] E. F. Codd. Further normalization of the database relational model. In Courant Computer Science Symposia 6: Data Base Systems, pages 33-64. Prentice-Hall, 1972.
[19] C. Delobel. Normalisation and hierarchical dependencies in the relational data model. ACM Trans. Database Syst., 3(3):201-222, 1978.
[20] J. Demetrovics, L. R´onyai, and H. Son. On the representation of dependencies by propositional logic. In MFDBS 91, volume 495 of Lecture Notes in Computer Science, pages 230-242. Springer, 1991.
[21] R. Fagin. Functional dependencies in a relational data base and propositional logic. IBM Journal of Research and Development, 21(6):543-544, 1977.
[22] R. Fagin. Multivalued dependencies and a new normal form for relational databases. ACM Trans. Database Syst., 2(3):262-278, 1977.
[23] R. Fagin. Horn clauses and database dependencies. J. ACM, 29(4):952-985, 1982.
[24] R. Fagin and M. Vardi. The theory of data dependencies - an overview. In ICALP, pages 1-22, 1984.
[25] R. Fagin and M. Y. Vardi. The theory of data dependencies: a survey. In Mathematics of Information Processing: Proceedings of Symposia in Applied Mathematics, pages 19-71. American Mathematical Society, 1986.
[26] W. Fan. XML constraints. In DEXA Workshops, pages 805-809. IEEE Computer Society, 2005.
[27] F. Ferrarotti, S. Hartmann, and S. Link. On the role of the complementation rule for data dependencies over incomplete relations. In WoLLIC, number 6188 in Lecture Notes in Artificial Intelligence, pages 136-147. Springer, 2010.
[28] P. C. Fischer, L. V. Saxton, S. J. Thomas, and D. Van Gucht. Interactions between dependencies and nested relational structures. J. Comput. Syst. Sci., 31(3):343-354, 1985.
[29] G. Graetzer. General Lattice Theory. Birkhauser, 1998.
[30] K. Hagihara, M. Ito, K. Taniguchi, and T. Kasami. Decision problems for multivalued dependencies in relational databases. SIAM J. Comput., 8(2):247-264, 1979.
[31] C. Hara and S. Davidson. Reasoning about nested functional dependencies. In PoDS, pages 91-100. ACM, 1999.
[32] S. Hartmann, M. Kirchberg, and S. Link. A subgraph-based approach towards functional dependencies for XML. In SCI, pages 200-205, 2003.
[33] S. Hartmann, H. K¨ohler, S. Link, T. Trinh, and J. Wang. On the notion of an XML key. In SDKB, number 4925 in Lecture Notes in Computer Science, pages 103-112. Springer, 2008.
[34] S. Hartmann and S. Link. More functional dependencies for XML. In AdBIS, number 2798 in Lecture Notes in Computer Science, pages 355-369. Springer, 2003.
[35] S. Hartmann and S. Link. On a problem of Fagin concerning multivalued dependencies in relational databases. Theor. Comput. Sci., 353(1-3):53-62, 2006.
[36] S. Hartmann and S. Link. Numerical constraints for XML. In WoLLIC, number 4576 in Lecture Notes in Computer Science, pages 203-217. Springer, 2007.
[37] S. Hartmann and S. Link. Unlocking keys for XML trees. In ICDT, number 4353 in Lecture Notes in Computer Science, pages 104-118. Springer, 2007.
[38] S. Hartmann and S. Link. Characterising nested database dependencies by fragments of propositional logic. Ann. Pure Appl. Logic, 152(1-3):84-106, 2008.
[39] S. Hartmann and S. Link. Efficient reasoning about a robust XML key fragment. ACM Trans. Database Syst., 34(2):Article 10, 2009.
[40] S. Hartmann and S. Link. Expressive, yet tractable XML keys. In EDBT, number 360 in ACM International Conference Proceeding Series, pages 357-367, 2009.
[41] S. Hartmann and S. Link. On inferences of weak multivalued dependencies. Fundam. Inform., 92(1-2):83-102, 2009.
[42] S. Hartmann and S. Link. Numerical constraints on XML data. Inf. Comput., 208(5):521-544, 2010.
[43] S. Hartmann and S. Link. When data dependencies over SQL tables meet the Logics of Paradox and S-3. In PoDS, pages 317-326, 2010.
[44] S. Hartmann, S. Link, and H. K¨ohler. Full hierarchical dependencies in fixed and undetermined universes. Ann. Math. Artif. Intell., 50(1-2):195-226, 2007.
[45] S. Hartmann, S. Link, and K.-D. Schewe. Axiomatisations of functional dependencies in the presence of records, lists, sets and multisets. Theor. Comput. Sci., 355(2):167-196, 2006.
[46] S. Hartmann, S. Link, and K.-D. Schewe. Functional and multivalued dependencies in nested databases generated by record and list constructor. Ann. Math. Artif. Intell., 46(1-2):114-164, 2006.
[47] S. Hartmann, S. Link, and T. Trinh. Solving the implication problem for XML functional dependencies with properties. In WoLLIC, number 6188 in Lecture Notes in Artificial Intelligence, pages 161-175. Springer, 2010.
[48] M. Ito, M. Iwasaki, K. Taniguchi, and K. Kasami. Membership problems for data dependencies in relational expressions. Theor. Comput. Sci., 34:315-335, 1984.
[49] V. Lakshmanan and C. VeniMadhavan. An algebraic theory of functional and multivalued dependencies in relational databases. Theor. Comput. Sci., 54:103-128, 1987.
[50] W.-D. Langeveldt and S. Link. Empirical evidence for the usefulness of Armstrong relations in the acquisition of meaningful functional dependencies. Inf. Syst., 35(3):352-374, 2010.
[51] M. Levene and G. Loizou. Axiomatisation of functional dependencies in incomplete relations. Theor. Comput. Sci., 206(1-2):283-300, 1998.
[52] L. Libkin. Elements of Finite Model Theory. Springer, 2006.
[53] S. Link. Consistency enforcement in databases. In Semantics in databases, volume 2582 of Lecture Notes in Computer Science, pages 139-159. Springer, 2001.
[54] S. Link. On multivalued dependencies in fixed and undetermined universes. In FoIKS, number 3861 in Lecture Notes in Computer Science, pages 257-276, 2006.
[55] S. Link. Charting the completeness frontier of inference systems for multivalued dependencies. Acta Inf., 45(7-8):565-591, 2008.
[56] S. Link. On the implication of multivalued dependencies in partial database relations. Int. J. Found. Comput. Sci., 19(3):691-715, 2008.
[57] D. Maier. The Theory of Relational Databases. Computer Science Press, 1983.
[58] H. Mannila and K.-J. Räihä. Design by example: An application of Armstrong relations. J. Comput. Syst. Sci., 33(2):126-141, 1986.
[59] A. Mendelzon. On axiomatising multivalued dependencies in relational databases. J. ACM, 26(1):37-44, 1979.
[60] J. Paredaens, P. De Bra, M. Gyssens, and D. Van Gucht. The Structure of the Relational Database Model. Springer, 1989.
[61] G. Priest. Logic of Paradox. Journal of Philosophical Logic, 8:219-241, 1979.
[62] Y. Sagiv. An algorithm for inferring multivalued dependencies with an application to propositional logic. J.ACM, 27(2):250-262, 1980.
[63] Y. Sagiv, C. Delobel, D. S. Parker Jr., and R. Fagin. An equivalence between relational database dependencies and a fragment of propositional logic. J. ACM, 28(3):435-453, 1981.
[64] M. Schaerf and M. Cadoli. Tractable reasoning via approximation. Artif. Intell., 74:249-310, 1995.
[65] D. Stott Parker Jr. and K. Parsaye-Ghomi. Inferences involving embedded multivalued dependencies and transitive dependencies. In SIGMOD, pages 52-57, 1980.
[66] Z. Tari, J. Stokes, and S. Spaccapietra. Object normal forms and dependency constraints for object-oriented schemata. ACM Trans. Database Syst., 22:513-569, 1997.
[67] B. Thalheim. Dependencies in Relational Databases. Teubner-Verlag, 1991.
[68] B. Thalheim. Entity-Relationship Modeling: Foundations of Database Technology. Springer, 2000.
[69] M. Vincent. Semantic foundation of 4NF in relational database design. Acta Inf., 36:1-41, 1999.
[70] M. Vincent, J. Liu, and C. Liu. Strong functional dependencies and their application to normal forms in XML. ACM Trans. Database Syst., 29(3):445-462, 2004.
[71] G. Weddell. Reasoning about functional dependencies generalized for semantic data models. ACM Trans. Database Syst., 17(1):32-64, 1992.
[72] J. Wijsen. Temporal FDs on complex objects. ACM Trans. Database Syst., 24(1):127-176, 1999.
[73] C. Yu and H. Jagadish. XML schema refinement through redundancy detection and normalization. VLDB J., 17(2):203-223, 2008.

Typ dokumentu

Bibliografia

Identyfikator YADDA

bwmeta1.element.baztech-article-BUS8-0012-0067