Geodesic
A generalization of the inference rules for join dependencies in databases
Modelirovanie i analiz informacionnyh sistem, Tome 27 (2020) no. 3, pp. 356-365.

Voir la notice de l'article provenant de la source Math-Net.Ru

In this paper a generalisation of the inference rules of the join dependencies that are used in the design of database schemas that meets the requirements of the fifth normal form is considered. In the previous works devoted to this problem, attempts to construct systems of the axioms of such dependencies based on inference rules are made. However, while the justification for the consistency (soundness) of the obtained axioms does not cause difficulties, the proof of completeness in general has not been satisfactorily resolved. First of all, this is due to the limitations of the inference rules themselves. This work focuses on two original axiom systems presented in the works of Sciore and Malvestuto. For the inclusion dependencies a system of rules that generalises existing systems and has fewer restrictions has been obtained. The paper presents a proof of the derivability of known systems of axioms from the presented inference rules. In addition, evidence of the consistency (soundness) of these rules is provided. The question of the completeness of the formal system based on the presented rules did not find a positive solution. In conclusion, the theoretical and practical significance of the inference rules for the join dependencies is noted.
Keywords: relational databases, join dependencies, inference rules. 
@article{MAIS_2020_27_3_a5,
     author = {S. V. Zykin},
     title = {A generalization of the inference rules for join dependencies in databases},
     journal = {Modelirovanie i analiz informacionnyh sistem},
     pages = {356--365},
     publisher = {mathdoc},
     volume = {27},
     number = {3},
     year = {2020},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/MAIS_2020_27_3_a5/}
}
TY  - JOUR
AU  - S. V. Zykin
TI  - A generalization of the inference rules for join dependencies in databases
JO  - Modelirovanie i analiz informacionnyh sistem
PY  - 2020
SP  - 356
EP  - 365
VL  - 27
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/MAIS_2020_27_3_a5/
LA  - ru
ID  - MAIS_2020_27_3_a5
ER  - 
%0 Journal Article
%A S. V. Zykin
%T A generalization of the inference rules for join dependencies in databases
%J Modelirovanie i analiz informacionnyh sistem
%D 2020
%P 356-365
%V 27
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/MAIS_2020_27_3_a5/
%G ru
%F MAIS_2020_27_3_a5
S. V. Zykin. A generalization of the inference rules for join dependencies in databases. Modelirovanie i analiz informacionnyh sistem, Tome 27 (2020) no. 3, pp. 356-365. http://geodesic.mathdoc.fr/item/MAIS_2020_27_3_a5/

[1] J. Ullman, Principles of Database Systems, Stanford University: Computer Science Press, 1980 | MR

[2] D. Maier, The theory of Relational Databases, Computer Science Press, Rockville, 1983 | MR | Zbl

[3] S. Abiteboul, R. Hull, V. Vianu, Foundations of Databases: The Logical Level, Addison-Wesley, 1994

[4] M. Casanova, R. Fagin, C. Papadimitriou, “Inclusion dependencies and their interaction with functional dependencies”, J. Comput. Syst. Sci., 28:1 (1984), 29–59 | DOI | MR | Zbl

[5] M. Levene, M. Vincent, “Justification for inclusion dependency normal form”, IEEE Trans. Knowl. Data Eng., 12:2 (2000), 281–291 | DOI

[6] H. Kohler, S. Link, “Inclusion dependencies reloaded”, The 24th ACM International on Conference on Information and Knowledge Management, CIKM'15, 2015, 1361–1370 | DOI

[7] V. Zykin, S. Zykin, “Analysis of Typed Inclusion Dependences with Null Values”, Automatic Control and Computer Sciences, 52:7 (2018), 638–646 | DOI | MR

[8] J. Rissanen, “Theory of relations for databases – a tutorial survey”, Mathematical Foundations of Computer Science 1978, ed. J. Winkowski, Springer, Berlin–Heidelberg, 1978, 536–551 | DOI | MR

[9] E. Sciore, “A Complete Axiomatization of Full Join Dependencies”, J. ACM, 29:2 (1982), 373–393 | DOI | Zbl

[10] C. Beeri, M. Vardi, “Formal systems for join dependencies”, Theoretical Computer Science, 38 (1985), 99–116 | DOI | MR | Zbl

[11] M. Gyssens, “On the complexity of join dependencies”, ACM Transactions on Database Systems, 11:1 (1986), 81–108 | DOI | MR | Zbl

[12] F. Malvestuto, “A Complete Axiomatization of Full Acyclic Join Dependencies”, Inf. Process. Lett., 68:3 (1998), 133–139 | DOI | MR | Zbl

[13] I. Düntsch, S. Mikulás, “Cylindric structures and dependencies in relational databases”, Theoretical Computer Science, 269 (2001), 451–468 | DOI | MR | Zbl

[14] S. Hartmann, H. Köhler, S. Link, “Full hierarchical dependencies in fixed and undetermined universes”, Annals of Mathematics and Artificial Intelligence, 50 (2007), 195–226 | DOI | MR | Zbl

[15] J. Biskup, S. Link, “Appropriate inferences of data dependencies in relational databases”, Annals of Mathematics and Artificial Intelligence, 63:3–4 (2011), 213–255 | DOI | MR | Zbl

[16] M. Hannula, J. Kontinen, “Anite axiomatization of conditional independence and inclusion dependencies”, Information and Computation, 249 (2016), 121–137 | DOI | MR | Zbl

[17] J. Baixeries, “A Formal Context for Acyclic Join Dependencies”, Lecture Notes in Computer Science, 10352, 2017, 563–572 | DOI

[18] S. Zykin, “Domains of functional dependences in databases”, Trudy Inst. Mat. i Mekh. UrO RAN, 22, no. 3, 2016, 117–129 | DOI | MR