Increasing the Efficiency of Minimal Key Enumeration Methods by Means of Parallelism

 

Abstract

Finding all minimal keys in a table is a hard problem but also provides a lot of benefits in database design and optimization. Some of the methods proposed in the literature are based on logic and, more specifically on tableaux paradigm. The size of the problems such methods deal with is strongly limited, which implies that they cannot be applied to big database schemas. We have carried out an experimental analysis to compare the results obtained by these methods in order to estimate their limits. Although tableaux paradigm may be viewed as a search space guiding the key finding task, none of the previous algorithms have incorporated parallelism. In this work, we have developed two different versions of the algorithms, a sequential and a parallel one, stating clearly how parallelism could naturally be integrated and the benefits we get over efficiency. This work has also guided future work guidelines to improve future designs of these methods.

Citation

Please, cite this work as:

[Pic+14] F. B. Picazo, P. Cordero, M. Enciso, et al. “Increasing the Efficiency of Minimal Key Enumeration Methods by Means of Parallelism”. In: ICSOFT-EA 2014 - Proceedings of the 9th International Conference on Software Engineering and Applications, Vienna, Austria, 29-31 August, 2014. Ed. by A. Holzinger, T. Libourel, L. A. Maciaszek and S. J. Mellor. SciTePress, 2014, pp. 512-517. DOI: 10.5220/0005108205120517. URL: https://doi.org/10.5220/0005108205120517.

BibTeX

@InProceedings{Picazo2014,
     author = {Fernando Benito Picazo and Pablo Cordero and Manuel Enciso and {’A}ngel Mora},
     booktitle = {{ICSOFT-EA} 2014 - Proceedings of the 9th International Conference on Software Engineering and Applications, Vienna, Austria, 29-31 August, 2014},
     title = {Increasing the Efficiency of Minimal Key Enumeration Methods by Means of Parallelism},
     year = {2014},
     editor = {Andreas Holzinger and Th{’e}r{`e}se Libourel and Leszek A. Maciaszek and Stephen J. Mellor},
     pages = {512–517},
     publisher = {SciTePress},
     bibsource = {dblp computer science bibliography, https://dblp.org},
     biburl = {https://dblp.org/rec/conf/icsoft/PicazoCEM14.bib},
     doi = {10.5220/0005108205120517},
     timestamp = {Fri, 23 Sep 2022 01:00:00 +0200},
     url = {https://doi.org/10.5220/0005108205120517},
}

Bibliometric data

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

Increasing the Efficiency of Minimal Key Enumeration Methods by Means of Parallelism

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.