×

Closure via functional dependence simplification. (English) Zbl 1257.68064

Summary: In this paper, a method for computing the closure of a set of attributes according to a specification of functional dependencies of the relational model is described. The main feature of this method is that it computes the closure using solely the inference system of the SL\(_{\mathsf{FD}}\) logic. For the first time, logic is used in the design of automated deduction methods to solve the closure problem. The strong link between the SL\(_{\mathsf{FD}}\) logic and the closure algorithm is presented and an SL\(_{\mathsf{FD}}\) simplification paradigm emerges as the key element of our method. In addition, the soundness and completeness of the closure algorithm are shown.
Our method has linear complexity, as the classical closure algorithms, and it has all the advantages provided by the use of logic. We have empirically compared our algorithm with the Diederich and Milton classical algorithm. This experiment reveals the best behaviour of our method which shows a significant improvement in the average speed.

MSC:

68P15 Database theory
03B70 Logic in computer science
68T30 Knowledge representation

Software:

Maude
PDF BibTeX XML Cite
Full Text: DOI

References:

[1] Adler, I. Tree-width and functional dependencies in databases. Proceedings of the Twenty-Seventh ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems. Vancouver, Canada. pp.311–320. New York, NY, USA PODS ’08, ACM
[2] Aguilera G., Lecture Notes in Artificial Intelligence 3171 pp 31– (2004)
[3] DOI: 10.1145/1059513.1059519 · Zbl 1311.94021
[4] Atzeni P., Relational Database Theory (1993)
[5] DOI: 10.1145/320064.320066
[6] DOI: 10.1093/jigpal/jzq017 · Zbl 06048174
[7] Belohlávek R., Lecture Notes in Computer Science 4068 pp 131– (2006)
[8] DOI: 10.1142/S0129054108005693 · Zbl 1149.68429
[9] DOI: 10.1145/373626.373697 · Zbl 05443950
[10] DOI: 10.1080/00207160902721797 · Zbl 1177.20078
[11] Cadoli M., Lecture Notes in Computer Science 3229 pp 628– (2004)
[12] DOI: 10.1016/S0166-218X(02)00209-3 · Zbl 1026.06008
[13] DOI: 10.1016/0306-4379(92)90017-H
[14] Clavel M., All About Maude – A High-Performance Logical Framework, How to Specify, Program and Verify Systems in Rewriting Logic (2007) · Zbl 1115.68046
[15] Codd E. F., The Relational Model for Database Management: Version 2 (1990) · Zbl 0809.68056
[16] DOI: 10.1016/S0004-3702(99)00013-2 · Zbl 0916.68128
[17] Cordero, P., Enciso, M., Pérez de Guzmán, I. and Mora, A. 2002.SLFD Logic: Elimination of Data Redundancy in Knowledge Representation, Vol. 2527, 141–150. Berlin, Heidelberg: Springer-Verlag. Lecture Notes in Artificial Intelligence · Zbl 1037.68136
[18] DOI: 10.1016/j.dam.2007.02.014 · Zbl 1142.68023
[19] Cordero, P., Enciso, M., Mora, A. and Pérez de Guzmán, I. A Complete Logic for Fuzzy Functional Dependencies Over Domains With Similarity Relations. IWANN ’09 Proceedings of the 10th International Work-Conference on Artificial Neural Networks: Part I: Bio-Inspired Systems: Computational and Ambient Intelligence. pp.261–269. Berlin, Heidelberg: Springer-Verlag. Lecture Notes in Computer Science, Vol. 5517, J. Cabestany, F. Sandoval, A. Prieto, and J.M. Corchado, eds.
[20] DOI: 10.1016/0166-218X(95)00076-4 · Zbl 0855.68025
[21] Demetrovics J., Serdica J. Comput 3 (2) pp 179– (2009)
[22] DOI: 10.1145/44498.44499
[23] Duck, G. J., Peyton-Jones, S., Stuckey, P. J. and Sulzmann, M. 2004.Sound and Decidable Type Inference for Functional Dependencies, Vol. 2986, 49–63. Berlin, Heidelberg: Springer-Verlag. Lecture Notes in Computer Science · Zbl 1126.68331
[24] DOI: 10.1147/rd.216.0534 · Zbl 0366.68022
[25] DOI: 10.1145/567112.567117 · Zbl 1326.68120
[26] Fan W., Proc. VLDB 1 (1) pp 391– (2008)
[27] DOI: 10.1093/jigpal/jzi050 · Zbl 1094.68018
[28] DOI: 10.1016/0004-3702(95)00040-2
[29] DOI: 10.1016/S0004-3702(98)00090-3 · Zbl 0909.68047
[30] Hartmann, S., Link, S. and Trinh, T. 2007.Efficient Reasoning About XFDs with Pre-image SemanticsVol. 4443, 1070–1074. Lecture Notes in Computer Science
[31] Hartmann, S., Link, S. and Trinh, T. 2010.Solving the Implication Problem for XML Functional Dependencies with Properties, Vol. 6188, 161–175. Berlin, Heidelberg: Springer-Verlag. Lecture Notes in Computer Science · Zbl 1253.68100
[32] Hermann, M. and Sertkaya, B. 2008.On the Complexity of Computing Generators of Closed Sets, Vol. 4933, 158–168. Berlin, Heidelberg: Springer-Verlag. Lecture Notes in Computer Science · Zbl 1131.68537
[33] DOI: 10.1016/S0004-3702(98)00114-3 · Zbl 0914.68185
[34] DOI: 10.1023/A:1023098325064 · Zbl 1023.68027
[35] DOI: 10.1109/61.108892
[36] Jones, M. P. 2000.Type Classes with Functional Dependencies, Vol. 1782, 230–244. Berlin, Heidelberg: Springer-Verlag. Lecture Notes in Computer Science · Zbl 0971.68641
[37] DOI: 10.1080/00207160903494147 · Zbl 1246.03047
[38] Lee, M. L., Ling, T. W. and Low, W. L. 2002.Designing Functional Dependencies for XML, Vol. 2287, 124–141. Berlin, Heidelberg: Springer-Verlag. Lecture Notes in Computer Science · Zbl 1054.68794
[39] DOI: 10.1007/3-540-46439-5_24
[40] Lv, T. and Yan, P. Mapping relational schemas to XML DTDs with constraints, Proceedings of the First International Multi-Symposiums on Computer and Computational Sciences. pp.528–533. Washington, DC, USA Hanzhou, Zhejiang, IMSCCS’06, Vol. 2, IEEE Computer Society
[41] Maier D., The Theory of Relational Databases (1983) · Zbl 0519.68082
[42] Mannila H., Design of Relational Databases (1992) · Zbl 0777.68014
[43] DOI: 10.1016/0169-023X(94)90023-X · Zbl 0805.68034
[44] Mendelzon, A. O. Functional dependencies in logic programs. Proceedings of 11th International Conference on Very Large Data Bases. pp.324–330.
[45] Mora, A., Enciso, M., Cordero, P. and Pérez de Guzmán, I. 2004.The Functional Dependence Implication Problem: Optimality and Minimality. An Efficient Preprocessing Transformation Based on the Substitution Paradigm, Vol. 3040, 136–146. Berlin, Heidelberg: Springer-Verlag. Lecture Notes in Artificial Intelligence
[46] Mora, A., Enciso, M., Cordero, P. and Pérez de Guzmán, I. SLfd logic in Prolog to remove redundancy in database. Proceedings of the International Conference on Computational and Mathematical Methods in Science and Engineering, CMMSE 2005, Alicante, Spain. pp.390–394. Vol. 1, J. Vigo Aguiar and B.A. Wade, eds.
[47] Mora, A., Enciso, M., Cordero, P. and Pérez de Guzmán, I. Logic-based functional dependencies programming. Proceedings of the International Conference on Computational and Mathematical Methods in Science and Engineering, CMMSE 2010, Almeria, Spain. pp.468–479. Vol. 1, J. Vigo Aguiar and B.A. Wade, eds.
[48] DOI: 10.1080/00207160.2010.484488 · Zbl 1237.68077
[49] Mora A., Iberoam. J. Artif. Intell 31 (10) pp 31– (2006)
[50] Paredaens J., EATCS Monographs on Theoretical Computer Science (1989)
[51] Press, W. H., Flannery, B. P., Teukolsky, S. A. and Vetterling, W. T. 1999. ”Numerical Recipes in C, The Art of Scientific Computing”. Cambridge: Cambridge University Press. · Zbl 0587.65003
[52] Savnik, I. and Flach, P. A. Bottom-up induction of functional dependencies from relations. Washington, DC, USA. Proceedings of AAAI-93 Workshop: Knowledge Discovery in Databases, pp.174–185. AAAI Press.
[53] DOI: 10.1002/mop.21057
[54] Thalheim, B. An overview on semantical constraints for database models. 6th International Conference, Intellectual Systems and Computer Science. Moscow, Russia. · Zbl 0842.68025
[55] Torgersen S., Automatic design of relational databases (1989)
[56] Tran, D. T. and Choi, E. 2006.Grid Resource Management Based on Functional Dependency, Vol. 4096, 365–374. Berlin, Heidelberg: Springer-Verlag. Embedded and Ubiquitous Computing, Lecture Notes in Computer Science
[57] Ullman J. D., Principles of Database Systems (1982) · Zbl 0558.68078
[58] Ullman J. D., Database and Knowledge-Base Systems (1988)
[59] DOI: 10.1007/s00236-007-0048-x · Zbl 1119.68072
[60] Wild, M. 1995.Computations With Finite Closure Systems and Implications, Vol. 959, 111–120. Berlin, Heidelberg: Springer-Verlag. Lecture Notes in Computer Science
[61] Yazici, A. and Karakaya, Z. 2007.JMathNorm: A Database Normalization Tool Using Mathematica, Vol. 4488, 186–193. Berlin, Heidelberg: Springer-Verlag. Lecture Notes in Computer Science
[62] DOI: 10.1145/319732.319749 · Zbl 0488.68061
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.