Analysis of typed inclusion dependencies with null values

V. S. Zykin ; S. V. Zykin

Modelirovanie i analiz informacionnyh sistem, Tome 24 (2017) no. 2, pp. 155-167.

Résumé

Null values have become an urgent problem since the creation of the relational data model. The impact of the uncertainty affects all types of dependencies used in the design and operation of the database. This fully applies to the inclusion dependencies, which are the theoretical basis for referential integrity on the data. Attempts to solve this problem contain inaccuracy in the statement of the problem and its solution. The errors in formulation of the problem can be associated with the use in the definition of untyped inclusion dependencies, which leads to permutations of the attributes, although, the attributes in database technology are identified by name and not by their place. In addition, linking with the use of the inclusion dependencies of heterogeneous attributes, even of the same type, is a sign of lost functional dependencies and leads to interaction of inclusion dependencies and non-trivial functional dependencies. Inaccuracies in the solution of the problem are contained in the statements of axioms and the proof of their properties, including completeness. In this paper we propose an original solution of this problem only for typed inclusion dependencies in the presence of Null values: a new axiom system is proposed, its completeness and soundness are proved. On the basis of inference rules we developed an algorithm for the construction of a not surplus set of typed inclusion dependencies. The correctness of the algorithm is proved.

Détail

Keywords: database, inclusion dependences, axiomatic, NULL values.

Bibliographie

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

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

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

[4] Chandra A. K., Vardi M. Y., “The Implication Problem for Functional and Inclusion Dependencies is Undecidable”, SIAM Journal on Computing, 14:3 (1985), 671–677 | DOI | MR | Zbl

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

[6] Kanellakis P. C., Cosmadakis S. S., Vardi M. Y., “Unary inclusion dependencies have polynomial time inference problems”, Proceedings of the fifteenth annual ACM symposium on Theory of computing, STOC '83 (New York, USA, 1983), 1983, 264–277

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

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

[9] Beeri C., Fagin R., Maier D., Yannakakis M., “On the Desirability of Acyclic Database Schemes”, Journal of the ACM, 38:3 (1983), 479–513 | DOI | MR

[10] Missaoui R., Godin R., “The Implication Problem for Inclusion Dependencies: A Graph Approach”, SIGMOD Record, 19:1 (1990), 36–40 | DOI

[11] Zykin V. S., “Ssylochnaya tselostnost dannykh v korporativnykh informatsionnykh sistemakh”, Informatika i ee primeneniya, 9:3 (2015), 119–127 (in Russian)

[12] Biskup J., Dublish P., “Objects in Relational Database Schemes with Functional, Inclusion and Exclusion Dependencies”, Theoretical Informatics and Applications, 27 (1993), 183–219 | DOI | MR | Zbl

[13] Johnson D. S., Klug A., “Testing Containment of Conjunctive Queries under Functional and Inclusion Dependencies”, Computer and System Sciences, 28 (1984), 167–189 | DOI | MR | Zbl

[14] Marchi F. D., Lopes S., Petit J. M., “Efficient Algorithms for Mining Inclusion Dependencies”, Advances in Database Technology - EDBT 2002 (Prague, Czech Republic, 2002), 2002, 199–214

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

[16] Bauckmann J., Abedjan Z., Leser U., Müller H., Naumann F., “Discovering conditional inclusion dependencies”, 21st ACM international conference on Information and knowledge management (CIKM '12) (ACM, New York, NY, USA), 2012, 2094–2098

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

[18] Visser J., “Coupled Transformation of Schemas, Documents, Queries, and Constraints”, Electronic Notes in Theoretical Computer Science, 200:3 (2008), 3–23 | DOI

[19] Garmany J., Walker J., Clark T., Logical Database Design Principles, CRC Press, Auerbach Publications, New York, NY, USA, 2005, 69 pp.

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

[21] Levene M., Loizou G., “Null Inclusion Dependencies in Relational Databases”, Information and Computation, 136:2 (1997), 67–108 | DOI | MR | Zbl

[22] Levene M., Loizou G., “The additivity problem for data dependencies in incomplete relational databases”, Semantics in Databases, Lecture Notes in Computer Science, 189, Springer-Verlag, Berlin–Heidelberg, 1998, 136–169 | DOI | MR

[23] Köhler H., Link S., “Inclusion Dependencies Reloaded”, The 24th ACM International on Conference on Information and Knowledge Management, CIKM '15, ACM, New York, NY, USA, 2015, 1361–1370