Abstract
We investigate structural and computational properties of Armstrong databases for a new class of possibilistic functional dependencies. We establish sufficient and necessary conditions for a given possibilistic relation to be Armstrong for a given set of possibilistic functional dependencies. We then use the characterization to compute Armstrong databases for any given set of these dependencies. The problem of finding an Armstrong database is precisely exponential in the input, but our algorithm computes an output whose size is always guaranteed to be at most quadratic in a minimum-sized output. Extensive experiments indicate that our algorithm shows good computational behavior on average. As our possibilistic functional dependencies have important applications in database design, our results indicate that Armstrong databases can effectively support business analysts during the acquisition of functional dependencies that are meaningful in a given application domain.
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
References
Arenas, M.: Normalization theory for XML. SIGMOD Rec. 35(4), 57–64 (2006)
Balamuralikrishna, N., Jiang, Y., Koehler, H., Leck, U., Link, S., Prade, H.: Possibilistic keys. Fuzzy Sets Syst. 376, 1–36 (2019)
Beeri, C., Dowd, M., Fagin, R., Statman, R.: On the structure of Armstrong relations for functional dependencies. J. ACM 31(1), 30–46 (1984)
Brown, P., Link, S.: Probabilistic keys. IEEE Trans. Knowl. Data Eng. 29(3), 670–682 (2017)
Calì, A., Calvanese, D., Lenzerini, M.: Data integration under integrity constraints. In: Seminal Contributions to Information Systems Engineering, 25 Years of CAiSE, pp. 335–352 (2013)
Codd, E.F.: A relational model of data for large shared data banks. Commun. ACM 13(6), 377–387 (1970)
Dubois, D., Prade, H.: Possibility theory and its applications: where do we stand? In: Kacprzyk, J., Pedrycz, W. (eds.) Springer Handbook of Computational Intelligence, pp. 31–60. Springer, Heidelberg (2015). https://doi.org/10.1007/978-3-662-43505-2_3
Fagin, R.: Horn clauses and database dependencies. J. ACM 29(4), 952–985 (1982)
Johnson, D.S., Klug, A.C.: Testing containment of conjunctive queries under functional and inclusion dependencies. J. Comput. Syst. Sci. 28(1), 167–189 (1984)
Köhler, H., Link, S.: SQL schema design: foundations, normal forms, and normalization. Inf. Syst. 76, 88–113 (2018)
Langeveldt, W.D., Link, S.: Empirical evidence for the usefulness of Armstrong relations in the acquisition of meaningful functional dependencies. Inf. Syst. 35(3), 352–374 (2010)
Link, S., Prade, H.: Possibilistic functional dependencies and their relationship to possibility theory. IEEE Trans. Fuzzy Syst. 24, 1–7 (2016)
Link, S., Prade, H.: Relational database schema design for uncertain data. Inf. Syst. 84, 88–110 (2019)
Mannila, H., Räihä, K.J.: Design by example: an application of Armstrong relations. J. Comput. Syst. Sci. 33(2), 126–141 (1986)
Marnette, B., Mecca, G., Papotti, P.: Scalable data exchange with functional dependencies. Proc. VLDB Endow. 3(1), 105–116 (2010)
Prokoshyna, N., Szlichta, J., Chiang, F., Miller, R.J., Srivastava, D.: Combining quantitative and logical data cleaning. Proc. VLDB Endow. 9(4), 300–311 (2015)
Ram, S.: Deriving functional dependencies from the entity-relationship model. Commun. ACM 38(9), 95–107 (1995)
Roblot, T., Hannula, M., Link, S.: Probabilistic cardinality constraints - validation, reasoning, and semantic summaries. VLDB J. 27(6), 771–795 (2018)
Roblot, T., Link, S.: Cardinality constraints and functional dependencies over possibilistic data. Data Knowl. Eng. 117, 339–358 (2018)
Selman, B., Kautz, H.A.: Knowledge compilation and theory approximation. J. ACM 43(2), 193–224 (1996)
Tan, H.B.K., Zhao, Y.: Automated elicitation of functional dependencies from source codes of database transactions. Inf. Software Technol. 46(2), 109–117 (2004)
Vincent, M.: Semantic foundations of 4NF in relational database design. Acta Inf. 36(3), 173–213 (1999)
Wei, Z., Hartmann, S., Link, S.: Discovery algorithms for embedded functional dependencies. In: Maier, D., Pottinger, R., Doan, A., Tan, W., Alawini, A., Ngo, H.Q. (eds.) Proceedings of the 2020 International Conference on Management of Data, SIGMOD Conference 2020, Online Conference [Portland, OR, USA], June 14–19, 2020. pp. 833–843. ACM (2020)
Wei, Z., Leck, U., Link, S.: Discovery and ranking of embedded uniqueness constraints. Proc. VLDB Endow. 12(13), 2339–2352 (2019)
Wei, Z., Link, S.: Embedded functional dependencies and data-completeness tailored database design. Proc. VLDB Endow. 12(11), 1458–1470 (2019)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2020 Springer Nature Switzerland AG
About this paper
Cite this paper
Jeong, S., Ma, H., Wei, Z., Link, S. (2020). Structural and Computational Properties of Possibilistic Armstrong Databases. In: Dobbie, G., Frank, U., Kappel, G., Liddle, S.W., Mayr, H.C. (eds) Conceptual Modeling. ER 2020. Lecture Notes in Computer Science(), vol 12400. Springer, Cham. https://doi.org/10.1007/978-3-030-62522-1_43
Download citation
DOI: https://doi.org/10.1007/978-3-030-62522-1_43
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-62521-4
Online ISBN: 978-3-030-62522-1
eBook Packages: Computer ScienceComputer Science (R0)