Generalization of typed include dependencies with null values in databases

S. V. Zykin

Modelirovanie i analiz informacionnyh sistem, Tome 30 (2023) no. 3, pp. 192-201.

Résumé

The paper discusses a new type of dependency in databases, which is a generalization of inclusion dependencies. Traditionally, such dependencies are used in practice to ensure referential integrity. In this case, the restriction is established only between a pair of relations, the first of which is called the main, the second is external. In practice, referential integrity often needs to be established for a larger number of relations, where several main and several external relations participate in the same constraint. Such a structure corresponds to an ultragraph. The paper provides a rationale for generalized inclusion dependencies that take into account the presence of null values in external relations. Based on the study of the properties of typed dependencies, a system of axioms is obtained, for which consistency (soundness) and completeness are proved.

Détail

Keywords: database, inclusion dependencies, axiomatics, null values.

Bibliographie

[1] J. Ullman, Principles of database systems, Stanford University: Computer Science Press, 1980, 484 pp. | MR

[2] D. Maier, The theory of relational databases, Rockville: Computer Science Press, 1983, 637 pp. | MR

[3] M. Casanova, R. Fagin, C. Papadimitriou, “Inclusion dependencies and their interaction with functional dependencies”, Journal of Computer and System Sciences, 28:1 (1984), 29–59 | DOI | MR | Zbl

[4] A. K. Chandra, M. Y. Vardi, “The implication problem for functional and inclusion dependencies is undecidable”, SIAM Journal on Computing, 14:3 (1985), 671–677 | DOI | MR | Zbl

[5] R. Fagin, M. Y. Vardi, “Armstrong databases for functional and inclusion dependencies”, Information Processing Letters, 16:1 (1983), 13–19 | DOI | MR | Zbl

[6] P. M. Kanellakis, R. Cosmadakis, M. Y. Vardi, “Unary inclusion dependencies have polynomial time inference problems”, Proceedings of the fifteenth annual acm symposium on theory of computing, 1983, 264–277 | DOI

[7] S. S. Cosmadakis, P. C. Kanellakis, M. Y. Vardi, “Polynomial-time implication problems for unary inclusion dependencies”, Association for Computing Machinery, 37:1 (1990), 15–46 | DOI | MR | Zbl

[8] M. Levene, M. W. Vincent, “Justification for inclusion dependency normal form”, IEEE Transactions on Knowledge and Data Engineering, 12:2 (2000), 281–291 | DOI | MR

[9] C. Beeri, R. Fagin, D. Maier, Y. M., “On the desirability of acyclic database schemes”, Association for Computing Machinery, 30:3 (1990), 479–513 | DOI | MR

[10] R. Missaoui, R. Godin, “The implication problem for inclusion dependencies: a graph approach”, ACM SIGMOD Record, 19:1 (1990), 36–40 | DOI

[11] M. Hannula, S. Link, “On the interaction of functional and inclusion dependencies with independence atoms”, Database systems for advanced applications, eds. J. Pei, Y. Manolopoulos, S. Sadiq, J. Li, Springer International Publishing, 2018, 353–369

[12] J. Biskup, P. Dublish, “Objects in relational database schemes with functional, inclusion and exclusion dependencies”, 3rd symposium on mathematical fundamentals of database and knowledge base systems, Springer, Berlin–Heidelberg, 1991, 276–290 | MR

[13] D. S. Johnson, A. Klug, “Testing containment of conjunctive queries under functional and inclusion dependencies”, Journal Computer and System Sciences, 28:1 (1984), 167–189 | DOI | MR | Zbl

[14] F. De Marchi, S. Lopes, J. Petit, “Efficient algorithms for mining inclusion dependencies”, Advances in database technology — EDBT 2002, eds. C. S. Jensen, S. Šaltenis, K. G. Jeffery, J. Pokorny, E. Bertino, K. Böhn, M. Jarke, Springer, Berlin–Heidelberg, 2002, 464–476 | DOI | Zbl

[15] J. Bauckmann, Z. Abedjan, H. Müller, F. Naumann, “Discovering conditional inclusion dependencies”, Proceedings of the 21st acm international conference on information and knowledge management, Association for Computing Machinery, 2012, 2094–2098

[16] M. T. Gómez-López, R. M. Gasca, J. M. Pérez-Álvarez, “Compliance validation and diagnosis of business data constraints in business processes”, Information Systems, 48 (2015), 26–43, Elsevier | DOI

[17] S. Ma, W. Fan, L. Bravo, “Extending inclusion dependencies with conditions”, Theoretical Computer Science, 515 (2014), 64–95 | DOI | MR | Zbl

[18] J. Visser, “Coupled transformation of schemas, documents, queries, and constraints”, Electronic Notes in Theoretical Computer Science, 200:3 (2008), 3–23 | DOI

[19] J. Garmany, J. Walker, T. Clark, Logical database design principles, Auerbach Publications, 1980, 200 pp.

[20] S. Lopes, J.-M. Petit, F. Toumani, “Discovering interesting inclusion dependencies: application to logical database tuning”, Information Systems, 27:1 (2002), 1–19 | DOI | Zbl

[21] Y. Kaminsky, E. Pena, F. Naumann, “Discovering similarity inclusion dependencies”, Proceedings of the ACM on Management of Data, 1:1 (2023), 1–24 | DOI

[22] M. Levene, G. Loizou, “Null inclusion dependencies in relational databases”, Information and Computation, 136:2 (1997), 67–108 | DOI | MR | Zbl

[23] M. Levene, G. Loizou, “The additivity problem for data dependencies in incomplete relational databases”, Semantics in databases, 1358, Springer, 1998, 136–169 | DOI | MR

[24] H. Köhler, S. Link, “Inclusion dependencies reloaded”, Proceedings of the 24th ACM international on conference on information and knowledge management, Association for Computing Machinery, New York, NY, USA, 2015, 1361–1370

[25] V. S. Zykin, S. V. Zykin, “Analysis of typed inclusion dependences with null values”, Automatic Control and Computer Sciences, 52:7 (2018), 638–646 | DOI | MR

[26] S. Zykin, “Domains of functional dependences in databases”, Trudy Instituta Matematiki i Mekhaniki UrO RAN, 22, no. 3, 2016, 117–129 (in Russian) | DOI | MR