Closure via functional dependence simplification
Abstract
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 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 FD logic and the closure algorithm is presented and an SL 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.
Citation
Please, cite this work as:
[Mor+12] Á. Mora, P. Cordero, M. Enciso, et al. “Closure via functional dependence simplification”. In: Int. J. Comput. Math. 89.4 (2012), pp. 510-526. DOI: 10.1080/00207160.2011.644275. URL: https://doi.org/10.1080/00207160.2011.644275.
Bibliometric data
The following data has been extracted from resources such as OpenAlex, Dimensions, PlumX or Altmetric.
- Citations
- CrossRef - Citation Indexes: 36
- Captures
- Mendeley - Readers: 9
Cites
The following graph plots the number of cites received by this work from its publication, on a yearly basis.
Papers citing this work
The following is a non-exhaustive list of papers that cite this work:
[1] R. Belohlavek, P. Cordero, M. Enciso, et al. “An Efficient Reasoning Method for Dependencies over Similarity and Ordinal Data”. In: Modeling Decisions for Artificial Intelligence. Springer Berlin Heidelberg, 2012, p. 408–419. ISBN: 9783642346200. DOI: 10.1007/978-3-642-34620-0_36. URL: http://dx.doi.org/10.1007/978-3-642-34620-0_36.
[2] P. Cordero, M. Enciso, D. López-Rodríguez, et al. “fcaR, Formal Concept Analysis with R”. In: The R Journal 14.1 (Jun. 2022), p. 341–361. ISSN: 2073-4859. DOI: 10.32614/rj-2022-014. URL: http://dx.doi.org/10.32614/rj-2022-014.
[3] P. Cordero, M. Enciso, D. López, et al. “A conversational recommender system for diagnosis using fuzzy rules”. In: Expert Systems with Applications 154 (Sep. 2020), p. 113449. ISSN: 0957-4174. DOI: 10.1016/j.eswa.2020.113449. URL: http://dx.doi.org/10.1016/j.eswa.2020.113449.
[4] P. Cordero, M. Enciso, A. Mora, et al. “Knowledge discovery in social networks by using a logic-based treatment of implications”. In: Knowledge-Based Systems 87 (Oct. 2015), p. 16–25. ISSN: 0950-7051. DOI: 10.1016/j.knosys.2015.07.018. URL: http://dx.doi.org/10.1016/j.knosys.2015.07.018.
[5] P. Cordero, M. Enciso, Á. Mora, et al. “A Formal Concept Analysis Approach to Cooperative Conversational Recommendation”. In: International Journal of Computational Intelligence Systems 13.1 (2020), p. 1243. ISSN: 1875-6883. DOI: 10.2991/ijcis.d.200806.001. URL: http://dx.doi.org/10.2991/ijcis.d.200806.001.
[6] P. Cordero, M. Enciso, A. Mora, et al. “A tableaux-like method to infer all minimal keys”. In: Logic Journal of IGPL 22.6 (Sep. 2014), p. 1019–1044. ISSN: 1368-9894. DOI: 10.1093/jigpal/jzu025. URL: http://dx.doi.org/10.1093/jigpal/jzu025.
[7] P. Cordero, M. Enciso, Á. Mora, et al. “Attribute implications with unknown information based on weak Heyting algebras”. In: Fuzzy Sets and Systems 490 (Aug. 2024), p. 109026. ISSN: 0165-0114. DOI: 10.1016/j.fss.2024.109026. URL: http://dx.doi.org/10.1016/j.fss.2024.109026.
[8] P. Cordero, M. Enciso, A. Mora, et al. “Parameterized simplification logic I: reasoning with implications and classes of closure operators”. In: International Journal of General Systems 49.7 (Oct. 2020), p. 724–746. ISSN: 1563-5104. DOI: 10.1080/03081079.2020.1831484. URL: http://dx.doi.org/10.1080/03081079.2020.1831484.
[9] R. Janostik, J. Konecny, and P. Krajča. “LinCbO: Fast algorithm for computation of the Duquenne-Guigues basis”. In: Information Sciences 572 (Sep. 2021), p. 223–240. ISSN: 0020-0255. DOI: 10.1016/j.ins.2021.04.104. URL: http://dx.doi.org/10.1016/j.ins.2021.04.104.
[10] J. Konecny and M. Ojeda-Aciego. “On homogeneousL-bonds and heterogeneousL-bonds”. In: International Journal of General Systems 45.2 (Oct. 2015), p. 160–186. ISSN: 1563-5104. DOI: 10.1080/03081079.2015.1072926. URL: http://dx.doi.org/10.1080/03081079.2015.1072926.
[11] O. Krídlo and M. Ojeda-Aciego. “Revising the link between L-Chu correspondences and completely lattice L-ordered sets”. In: Annals of Mathematics and Artificial Intelligence 72.1–2 (Apr. 2014), p. 91–113. ISSN: 1573-7470. DOI: 10.1007/s10472-014-9416-8. URL: http://dx.doi.org/10.1007/s10472-014-9416-8.
[12] M. Ojeda-Hernández and D. López-Rodríguez. “On Direct Systems of Implications with Graded Attributes”. In: Advances in Fuzzy Logic and Technology. Springer Nature Switzerland, 2025, p. 146–157. ISBN: 9783031972287. DOI: 10.1007/978-3-031-97228-7_13. URL: http://dx.doi.org/10.1007/978-3-031-97228-7_13.
[13] M. Ojeda-Hernández, D. López-Rodríguez, and Á. Mora. “A Formal Concept Analysis approach to hierarchical description of malware threats”. In: Forensic Science International: Digital Investigation 50 (Sep. 2024), p. 301797. ISSN: 2666-2817. DOI: 10.1016/j.fsidi.2024.301797. URL: http://dx.doi.org/10.1016/j.fsidi.2024.301797.
[14] F. Pérez-Gámez and C. Bejines. “An exploration of weak Heyting algebras: Characterization and properties”. In: International Journal of Approximate Reasoning 179 (Apr. 2025), p. 109365. ISSN: 0888-613X. DOI: 10.1016/j.ijar.2025.109365. URL: http://dx.doi.org/10.1016/j.ijar.2025.109365.
[15] F. Pérez-Gámez, P. Cordero, M. Enciso, et al. “Simplification logic for the management of unknown information”. In: Information Sciences 634 (Jul. 2023), p. 505–519. ISSN: 0020-0255. DOI: 10.1016/j.ins.2023.03.015. URL: http://dx.doi.org/10.1016/j.ins.2023.03.015.
[16] F. Pérez-Gámez, D. López-Rodríguez, P. Cordero, et al. “Simplifying Implications with Positive and Negative Attributes: A Logic-Based Approach”. In: Mathematics 10.4 (Feb. 2022), p. 607. ISSN: 2227-7390. DOI: 10.3390/math10040607. URL: http://dx.doi.org/10.3390/math10040607.
[17] E. Rodríguez-Lorenzo, K. Adaricheva, P. Cordero, et al. “Formation of the D-basis from implicational systems using Simplification logic”. In: International Journal of General Systems 46.5 (Jul. 2017), p. 547–568. ISSN: 1563-5104. DOI: 10.1080/03081079.2017.1349632. URL: http://dx.doi.org/10.1080/03081079.2017.1349632.
[18] E. Rodríguez-Lorenzo, K. Bertet, P. Cordero, et al. “Direct-optimal basis computation by means of the fusion of simplification rules”. In: Discrete Applied Mathematics 249 (Nov. 2018), p. 106–119. ISSN: 0166-218X. DOI: 10.1016/j.dam.2017.12.031. URL: http://dx.doi.org/10.1016/j.dam.2017.12.031.
[19] E. Rodríguez-Lorenzo, P. Cordero, M. Enciso, et al. “Canonical dichotomous direct bases”. In: Information Sciences 376 (Jan. 2017), p. 39–53. ISSN: 0020-0255. DOI: 10.1016/j.ins.2016.10.004. URL: http://dx.doi.org/10.1016/j.ins.2016.10.004.
[20] J. M. Rodríguez‐Jiménez, P. Cordero, M. Enciso, et al. “Data mining algorithms to compute mixed concepts with negative attributes: an application to breast cancer data analysis”. In: Mathematical Methods in the Applied Sciences 39.16 (Jan. 2016), p. 4829–4845. ISSN: 1099-1476. DOI: 10.1002/mma.3814. URL: http://dx.doi.org/10.1002/mma.3814.
[21] N. Shadab, T. Cody, A. Salado, et al. “A Systems-Theoretical Formalization of Closed Systems”. In: IEEE Open Journal of Systems Engineering 2 (2024), p. 26–37. ISSN: 2771-9987. DOI: 10.1109/ojse.2024.3369070. URL: http://dx.doi.org/10.1109/ojse.2024.3369070.