×

Non-deterministic ideal operators: an adequate tool for formalization in data bases. (English) Zbl 1142.68023

Summary: We propose the application of formal methods to software engineering. The most used data model is the relational model and we present, within the general framework of lattice theory, this analysis of functional dependencies. For this reason, we characterize the concept of \(f\)-family by means of a new concept which we call non-deterministic ideal operator (nd.ideal-o). The study of nd.ideal-o.s allows us to obtain results about functional dependencies as trivial particularizations, to clarify the semantics of the functional dependencies and to progress in their efficient use, and to extend the concept of schema. Moreover, the algebraic characterization of the concept of key of a schema allows us to propose new formal definitions in the lattice framework for classical normal forms in relation schemata. We give a formal definition of the normal forms for functional dependencies more frequently used in the bibliography: the second normal form, the third normal form and Boyce-Codd’s normal form.

MSC:

68N30 Mathematical aspects of software engineering (specification, verification, metrics, requirements, etc.)
68P15 Database theory
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] G. Aguilera, P. Cordero, M. Enciso, A. Mora, I.P. de Guzmán, A non-explosive treatment of functional dependencies using rewriting logic, Lecture Notes in Artificial Intelligence, vol. 3171, Springer, Berlin, 2004, pp. 31-40.; G. Aguilera, P. Cordero, M. Enciso, A. Mora, I.P. de Guzmán, A non-explosive treatment of functional dependencies using rewriting logic, Lecture Notes in Artificial Intelligence, vol. 3171, Springer, Berlin, 2004, pp. 31-40. · Zbl 1105.68340
[2] W.W. Armstrong, Dependency structures of data base relationships, in: Proceedings of the IFIP Congress, North-Holland, Amsterdam, 1974, pp. 580-583.; W.W. Armstrong, Dependency structures of data base relationships, in: Proceedings of the IFIP Congress, North-Holland, Amsterdam, 1974, pp. 580-583. · Zbl 0296.68038
[3] Atzeni, P.; Antonellis, V. D., Relational Database Theory (1993), The Benjamin/Cummings Publishing Company Inc.: The Benjamin/Cummings Publishing Company Inc. Menlo Park, CA · Zbl 0771.68013
[4] Bell, D. A., From data properties to evidence, IEEE Trans. Knowledge and Data Eng., 5, 6, 965-968 (1993)
[5] J. Biskup, J.v.d. Bussche, P.D. Bra, J. Demetrovics, G. Gottlob, S. Hegner, A. Heuer, G. Katona, H. Nam Son, J. Paredaens, L. Tenenbaum, B. Thalheim, in: International Symposium on Foundations of Information and Knowledge Systems—FOIKS, \( \langle;\) http://www.informatik.tu-cottbus.de/ foiks/home.html \(\rangle;\).; J. Biskup, J.v.d. Bussche, P.D. Bra, J. Demetrovics, G. Gottlob, S. Hegner, A. Heuer, G. Katona, H. Nam Son, J. Paredaens, L. Tenenbaum, B. Thalheim, in: International Symposium on Foundations of Information and Knowledge Systems—FOIKS, \( \langle;\) http://www.informatik.tu-cottbus.de/ foiks/home.html \(\rangle;\).
[6] P. Buneman, S. Davidson, W. Fan, C. Hara, W. Tan, Reasoning about keys for XML, Draft manuscript, 2000.; P. Buneman, S. Davidson, W. Fan, C. Hara, W. Tan, Reasoning about keys for XML, Draft manuscript, 2000.
[7] P. Buneman, W. Fan, J. ’. r.o.m. SiméÉ, S. Weinstein, Constraints for semistructured data and XML, SIGMOD Record, ACM Special Interest Group on Management of Data, vol. 30(1), 2001, pp. 47-54.; P. Buneman, W. Fan, J. ’. r.o.m. SiméÉ, S. Weinstein, Constraints for semistructured data and XML, SIGMOD Record, ACM Special Interest Group on Management of Data, vol. 30(1), 2001, pp. 47-54.
[8] Caspard, N.; Monjardet, B., The lattices of closure systems, closure operators, and implicational systems on a finite set: a survey, Discrete Appl. Math., 127, 2, 241-269 (2003) · Zbl 1026.06008
[9] Codd, E. F., The Relational Model for Database Management: Version 2 (1990), Addison-Wesley: Addison-Wesley Reading, MA · Zbl 0809.68056
[10] P. Cordero, M. Enciso, I.P. de Guzmán, A. Mora, SLFD logic: elimination of data redundancy in knowledge representation, Lecture Notes in Artificial Intelligence, vol. 2527, Advances in AI, Iberamia, Springer, Berlin, 2002, pp. 141-150.; P. Cordero, M. Enciso, I.P. de Guzmán, A. Mora, SLFD logic: elimination of data redundancy in knowledge representation, Lecture Notes in Artificial Intelligence, vol. 2527, Advances in AI, Iberamia, Springer, Berlin, 2002, pp. 141-150. · Zbl 1037.68136
[11] P. Cordero, M. Enciso, A. Mora, I.P. de Guzmán, Ideal non-deterministic operators as a formal framework to reduce the key problem, Inform. and Comput., submitted for publication.; P. Cordero, M. Enciso, A. Mora, I.P. de Guzmán, Ideal non-deterministic operators as a formal framework to reduce the key problem, Inform. and Comput., submitted for publication. · Zbl 1237.68077
[12] Cordero, P.; Gutiérrez, G.; Martínez, J.; de Guzmán, I. P., A new algebraic tool for automatic theorem provers. Multisemilattice: a structure to improve the efficiency of provers in temporal logics, Ann. Math. Artificial Intelligence, 42, 369-398 (2004) · Zbl 1095.68110
[13] Davey, B. A.; Priestley, H. A., Introduction to Lattices and Order (1990), Cambridge University Press: Cambridge University Press Cambridge · Zbl 0701.06001
[14] Demetrovics, J.; Libkin, L.; Muchnik, I. B., Functional dependencies in relational databases: a lattice point of view, Discrete Appl. Math., 40, 155-185 (1992) · Zbl 0767.68029
[15] Demetrovics, J.; Thi, V. D., Some results about functional dependencies, Acta Cybern. Hungary, VIII, 3, 273-278 (1988) · Zbl 0662.68109
[16] Demetrovics, J.; Thi, V. D., Family of functional dependencies and its equivalent descriptions, Comput. Math. Appl., 29, 4, 101-109 (1995) · Zbl 0830.68035
[17] Demetrovics, J.; Vu, D. T., Some results about normal forms for functional dependency in the relational datamodel, Discrete Appl. Math., 69, 61-74 (1996) · Zbl 0855.68025
[18] W. Fan, L. Libkin, On XML integrity constraints in the presence of DTDs, in: Symposium on Principles of Database Systems, 2001.; W. Fan, L. Libkin, On XML integrity constraints in the presence of DTDs, in: Symposium on Principles of Database Systems, 2001. · Zbl 1326.68120
[19] Flach, P. A.; Savnik, I., Database dependency discovery: a machine learning approach, AI Comm., 12, 139-160 (1999)
[20] Gottlob, G.; Libkin, L., Investigations on Armstrong relations, dependency inference and excluded functional dependencies, Acta Cybern., 9, 4, 385-402 (1990) · Zbl 0727.68026
[21] Gratzer, G., General Lattice Theory (1998), Birkhauser Verlag · Zbl 0385.06015
[22] Guan, J. W.; Bell, D. A., Rough computational methods for information systems, Artificial Intelligence, 105, 77-103 (1998) · Zbl 0909.68047
[23] Mter Hofstede, A. H.; Lippe, E.; van der Weide, T. P., Applications of a categorical framework for conceptual data modeling, Acta Inform., 34, 927-963 (1997) · Zbl 0898.68024
[24] S.M.G. IBM Research, Dependencies in distributed service management, Research Project, \( \langle;\) http://www.research.ibm.com/sysman/\( \rangle;\), 2003.; S.M.G. IBM Research, Dependencies in distributed service management, Research Project, \( \langle;\) http://www.research.ibm.com/sysman/\( \rangle;\), 2003.
[25] M.L. Lee, T.W. Ling, W.L. Low, Designing functional dependencies for XML, Lecture Notes in Computer Science, EDTB 2002 Proceedings 2287, Springer, Berlin, 2002, pp. 124-141.; M.L. Lee, T.W. Ling, W.L. Low, Designing functional dependencies for XML, Lecture Notes in Computer Science, EDTB 2002 Proceedings 2287, Springer, Berlin, 2002, pp. 124-141. · Zbl 1054.68794
[26] H. Mannila, Methods and problems in data mining, in: N. Afrati, P.G. Kolaitis (Eds.), Proceedings of International Conference on Database Theory, 17(2), 1997.; H. Mannila, Methods and problems in data mining, in: N. Afrati, P.G. Kolaitis (Eds.), Proceedings of International Conference on Database Theory, 17(2), 1997. · Zbl 1056.68516
[27] Mannila, H.; Raiha, K.-J., Algorithms for inferring functional dependencies from relations, Data and Knowledge Eng., 12, 83-99 (1994) · Zbl 0805.68034
[28] Martin, N. M.; Pollard, S., Closure Spaces and Logic (1996), Kluwer Academic Publishers: Kluwer Academic Publishers Dordrecht · Zbl 0855.54001
[29] J. Martínez, P. Cordero, G. Gutiérrez, I.P. de Guzmán, Generalizations of lattices looking at computation, Discrete Math. 295 (2005) 107-141.; J. Martínez, P. Cordero, G. Gutiérrez, I.P. de Guzmán, Generalizations of lattices looking at computation, Discrete Math. 295 (2005) 107-141.
[30] Martínez, J.; Gutiérrez, G.; de Guzmán, I. P.; Cordero, P., Restricted Ideals and the groupability property. Tools for temporal reasoning, Kybernetika, 39, 5, 521-546 (2003) · Zbl 1249.03004
[31] Y. Men-hin, A. Wai-Chee Fu, From XML to relational databases, Knowledge Representation Meets Databases, 2001.; Y. Men-hin, A. Wai-Chee Fu, From XML to relational databases, Knowledge Representation Meets Databases, 2001.
[32] A. Mora, M. Enciso, P. Cordero, G. Aguilera, I.P. de Guzmán, A new closure algorithm based in logic: SLFD-Closure versus classical closures. Revista Iberoamericana de Inteligencia Artificial 31 (2006) 31-40.; A. Mora, M. Enciso, P. Cordero, G. Aguilera, I.P. de Guzmán, A new closure algorithm based in logic: SLFD-Closure versus classical closures. Revista Iberoamericana de Inteligencia Artificial 31 (2006) 31-40.
[33] A. Mora, M. Enciso, P. Cordero, I.P. de Guzmán, An efficient preprocessing transformation for functional dependencies sets based on the substitution paradigm, Lecture Notes in Artificial Intelligence, vol. 3040, Springer, Berlin, 2004, pp. 136-146.; A. Mora, M. Enciso, P. Cordero, I.P. de Guzmán, An efficient preprocessing transformation for functional dependencies sets based on the substitution paradigm, Lecture Notes in Artificial Intelligence, vol. 3040, Springer, Berlin, 2004, pp. 136-146.
[34] T. Niemi, J. Nummenmaa, P. Thanisch, Logical multidimensional database design for ragged and unbalanced aggregation, Design and Management of Data Warehouses, 2001.; T. Niemi, J. Nummenmaa, P. Thanisch, Logical multidimensional database design for ragged and unbalanced aggregation, Design and Management of Data Warehouses, 2001.
[35] Stumme, G.; Taouil, R.; Bastide, Y.; Pasquier, N.; Lakhal, L., Functional and embedded dependency inference: a data mining point of view, Inform. Systems, 26, 7, 477-506 (2002)
[36] B. Thalheim, An overview on semantical constraints for database models, in: Sixth International Conference, Intellectual Systems and Computer Science, 1996.; B. Thalheim, An overview on semantical constraints for database models, in: Sixth International Conference, Intellectual Systems and Computer Science, 1996.
[37] Ullman, J. D., Database and Knowledge-Base Systems (1988), Computer Science Press: Computer Science Press Rockville, MD
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.