Abstract
As yet another semantically enriched data model, we consider relational schemas with finite domain sizes and multiplicity bounds and diversity bounds together with functional dependencies as semantic constraints. As a simple variant of cardinality constraints, for a set of attributes, a multiplicity bound requires that a possible value combination occurs at most as often as the bound extension says. As a new kind of constraint, for a set of attributes, a diversity bound describes how many different value combinations under these attributes may at most occur in a relation instance. A multiplicity bound and a diversity bound together are seen as a weak abstraction of a so-called structure for the set of attributes on the left-hand side of a functional dependency. Such a structure specifies the exact size of the active domain of that set and the respective exact numbers of occurrences, summing up to a given instance size. We study how multiplicity bounds, diversity bounds and functional dependencies under finite sizes of attribute domains interact. We exhibit a powerful sound derivation system for all these items, together with a generation procedure for approximating the entailment closure of such constraints. We further analyze how to construct relation instances that exactly achieve the strongest entailed multiplicity or diversity bound extension, respectively, for some attribute set or even all of them.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
In the literature, there is no common agreement on the size of domains. Depending on their prevailing interests, whether more logically oriented or more combinatorially, authors deal exclusively with infinite domains, exclusively with finite domains, or both kinds, see, e.g., [1, 4, 6, 16, 18, 20, 21] and many other work.
- 2.
Levene/Loizou [18], Sect. 3.7 briefly mentions it in a note added to Def. 3.100.
- 3.
W.l.o.g., we only treat attribute domains of the kind \( dom _{ att } = \{1,\dots ,k_{ att }\}\).
- 4.
We use \( dom /k\) as an abbreviation to denote these two related functions on \(\mathcal {U}\).
- 5.
An instance r is a finite set, since all declared domains are finite.
- 6.
W.l.o.g. we always assume that the set is nonempty.
References
Abiteboul, S., Hull, R., Vianu, V.: Foundations of Databases. Addison-Wesley, Reading (1995)
Armstrong, W.W.: Dependency structures of data base relationships. In: IFIP Congress, pp. 580–583 (1974)
Berens, M., Biskup, J.: On sampling representatives of relational schemas with a functional dependency. In: Varzinczak, I. (ed.) FoIKS 2022. LNCS, vol. 13388, pp. 1–19. Springer, Cham (2022). https://doi.org/10.1007/978-3-031-11321-5_1
Berens, M., Biskup, J., Preuß, M.: Uniform probabilistic generation of relation instances satisfying a functional dependency. Inf. Syst. 103, 101848 (2022)
Biskup, J.: Inferences of multivalued dependencies in fixed and undetermined universes. Theor. Comput. Sci. 10, 93–105 (1980)
Biskup, J., Bonatti, P.A.: Controlled query evaluation with open queries for a decidable relational submodel. Ann. Math. Artif. Intell. 50(1–2), 39–77 (2007)
Biskup, J., Link, S.: Appropriate inferences of data dependencies in relational databases. Ann. Math. Artif. Intell. 63(3–4), 213–255 (2011)
Biskup, J., Preuß, M.: Can we probabilistically generate uniformly distributed relation instances efficiently? In: Darmont, J., Novikov, B., Wrembel, R. (eds.) ADBIS 2020. LNCS, vol. 12245, pp. 75–89. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-54832-2_8
Chen, P.P.: The entity-relationship model - toward a unified view of data. ACM Trans. Database Syst. 1(1), 9–36 (1976)
Demetrovics, J., Katona, G.O.H., Miklós, D., Thalheim, B.: On the number of independent functional dependencies. In: Dix, J., Hegner, S.J. (eds.) FoIKS 2006. LNCS, vol. 3861, pp. 83–91. Springer, Heidelberg (2006). https://doi.org/10.1007/11663881_6
Flajolet, P., Sedgewick, R.: Analytic Combinatorics. Cambridge University Press, Cambridge (2009)
Hannula, M., Kontinen, J., Link, S.: On the finite and general implication problems of independence atoms and keys. J. Comput. Syst. Sci. 82(5), 856–877 (2016)
Hartmann, S.: On the implication problem for cardinality constraints and functional dependencies. Ann. Math. Artif. Intell. 33(2–4), 253–307 (2001)
Hartmann, S., Köhler, H., Leck, U., Link, S., Thalheim, B., Wang, J.: Constructing Armstrong tables for general cardinality constraints and not-null constraints. Ann. Math. Artif. Intell. 73(1–2), 139–165 (2015)
Hartmann, S., Köhler, H., Link, S.: Full hierarchical dependencies in fixed and undetermined universes. Ann. Math. Artif. Intell. 50(1–2), 195–226 (2007)
Katona, G.O.H., Tichler, K.: Encoding databases satisfying a given set of dependencies. In: Lukasiewicz, T., Sali, A. (eds.) FoIKS 2012. LNCS, vol. 7153, pp. 203–223. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-28472-4_12
Kolahi, S., Libkin, L.: An information-theoretic analysis of worst-case redundancy in database design. ACM Trans. Database Syst. 35(1), 5:1–5:32 (2010)
Levene, M., Loizou, G.: A Guided Tour of Relational Databases and Beyond. Springer, London (1999). https://doi.org/10.1007/978-0-85729-349-7
Makowsky, J.A., Ravve, E.V.: The fundamental problem of database design. In: Plášil, F., Jeffery, K.G. (eds.) SOFSEM 1997. LNCS, vol. 1338, pp. 53–69. Springer, Heidelberg (1997). https://doi.org/10.1007/3-540-63774-5_97
Paredaens, J., Bra, P.D., Gyssens, M., Gucht, D.V.: The Structure of the Relational Database Model. EATCS Monographs on Theoretical Computer Science, vol. 17. Springer, Berlin (1989). https://doi.org/10.1007/978-3-642-69956-6
Thalheim, B.: Entity-Relationship Modeling – Foundations of Database Technology. Springer, Heidelberg (2000). https://doi.org/10.1007/978-3-662-04058-4
Thalheim, B.: Semiotics in databases. In: Schewe, K.-D., Singh, N.K. (eds.) MEDI 2019. LNCS, vol. 11815, pp. 3–19. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-32065-2_1
Vincent, M.W., Srinivasan, B.: Redundancy and the justification for fourth normal form in relational databases. Int. J. Found. Comput. Sci. 4(4), 355–365 (1993)
Wei, Z., Link, S.: Discovery and ranking of functional dependencies. In: ICDE 2019, pp. 1526–1537. IEEE (2019)
Acknowledgements
I would like to sincerely thank Sven Hartman and Sebastian Link for greatly stimulating discussions on early ideas about the topic of this work, and the anonymous reviewers for helpful and constructive remarks about the submitted version.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2024 The Author(s), under exclusive license to Springer Nature Switzerland AG
About this paper
Cite this paper
Biskup, J. (2024). Relational Schemas with Multiplicity Bounds, Diversity Bounds and Functional Dependencies. In: Meier, A., Ortiz, M. (eds) Foundations of Information and Knowledge Systems. FoIKS 2024. Lecture Notes in Computer Science, vol 14589. Springer, Cham. https://doi.org/10.1007/978-3-031-56940-1_3
Download citation
DOI: https://doi.org/10.1007/978-3-031-56940-1_3
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-031-56939-5
Online ISBN: 978-3-031-56940-1
eBook Packages: Computer ScienceComputer Science (R0)