Ideal non-deterministic operators as a formal framework to reduce the key finding problem

uncategorised

Authors

Ángel Mora

Inmaculada Perez de Guzmán

Manuel Enciso

Pablo Cordero

Published

1 January 2011

Publication details

Int. J. Comput. Math. vol. 88 (9), pages 1860–1868.

Links

Abstract

Abstract A formal development in the framework of the lattice theory for functional dependencies and minimal keys is presented. Beyond this theoretical study, a technique to prune the key finding problem, named scheme pruning transformation, is proposed in this work. This transformation is founded on theoretical results and has linear cost in the worst case. Moreover, this approach has provided a better size reduction than the usual techniques existing in the literature. Keywords: functional dependenceminimal keylattice theory 2000 AMS Subject Classifications : 06B1068P15H.2.0 Acknowledgements This paper has been partially supported by the Spanish project TIN2007-65819 and the Andalusian project P06-FQM-02049. We are grateful to the referees for their suggestions, which had lead to improve the paper itself and our future work. Notes From now on, the elements of will be denoted by juxtaposition and without braces. That is, abc denotes the subset {a, b, c}.

Citation

Please, cite this work as:

[Mor+11] Á. Mora, I. P. de Guzmán, M. Enciso, et al. “Ideal non-deterministic operators as a formal framework to reduce the key finding problem”. In: Int. J. Comput. Math. 88.9 (2011), pp. 1860-1868. DOI: 10.1080/00207160.2010.484488. URL: https://doi.org/10.1080/00207160.2010.484488.

BibTeX

@Article{Mora2011,
     author = {{’A}ngel Mora and Inmaculada Perez {de Guzm{’a}n} and Manuel Enciso and Pablo Cordero},
     journal = {Int. J. Comput. Math.},
     title = {Ideal non-deterministic operators as a formal framework to reduce the key finding problem},
     year = {2011},
     number = {9},
     pages = {1860–1868},
     volume = {88},
     bibsource = {dblp computer science bibliography, https://dblp.org},
     biburl = {https://dblp.org/rec/journals/ijcm/MoraGEC11.bib},
     doi = {10.1080/00207160.2010.484488},
     timestamp = {Fri, 23 Sep 2022 01:00:00 +0200},
     url = {https://doi.org/10.1080/00207160.2010.484488},
}

Bibliometric data

The following data has been extracted from resources such as OpenAlex, Dimensions, PlumX or Altmetric.

Citations
CrossRef - Citation Indexes: 6
Scopus - Citation Indexes: 7

Captures
Mendeley - Readers: 6

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] F. Benito-Picazo, P. Cordero, M. Enciso, et al. “Reducing the search space by closure and simplification paradigms: A parallel key finding method”. In: The Journal of Supercomputing 73.1 (Jan. 2016), p. 75–87. ISSN: 1573-0484. DOI: 10.1007/s11227-016-1622-1. URL: http://dx.doi.org/10.1007/s11227-016-1622-1.

[2] 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.

[3] J. Medina and M. Ojeda-Aciego. “Dual multi-adjoint concept lattices”. In: Information Sciences 225 (Mar. 2013), p. 47–54. ISSN: 0020-0255. DOI: 10.1016/j.ins.2012.10.030. URL: http://dx.doi.org/10.1016/j.ins.2012.10.030.

[4] A. Mora, P. Cordero, M. Enciso, et al. “Closure via functional dependence simplification”. In: International Journal of Computer Mathematics 89.4 (Mar. 2012), p. 510–526. ISSN: 1029-0265. DOI: 10.1080/00207160.2011.644275. URL: http://dx.doi.org/10.1080/00207160.2011.644275.

[5] 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.

[6] V. Q. Tuấn and H. Thuần. “Một số kết quả về thuật toán tính bao đóng và rút gọn bài toán tìm khóa của lược đồ quan hệ”. In: Research and Development on Information and Communication Technology (Nov. 2017). ISSN: 1859-3526. DOI: 10.32913/rd-ict.vol2.no38.364. URL: http://dx.doi.org/10.32913/rd-ict.vol2.no38.364.

[7] J. Viaud, K. Bertet, R. Missaoui, et al. “Distributed and Parallel Computation of the Canonical Direct Basis”. In: Formal Concept Analysis. Springer International Publishing, 2017, p. 228–241. ISBN: 9783319592718. DOI: 10.1007/978-3-319-59271-8_15. URL: http://dx.doi.org/10.1007/978-3-319-59271-8_15.

[8] J. Vigo-Aguiar and J. A. Lopez-Ramos. “Applications of computational mathematics in science and engineering”. In: International Journal of Computer Mathematics 88.9 (Jun. 2011), p. 1805–1807. ISSN: 1029-0265. DOI: 10.1080/00207160.2011.578828. URL: http://dx.doi.org/10.1080/00207160.2011.578828.