Proceedings

Automated Reasoning to Infer all Minimal Keys

Download BibTeX Cite

Proceedings of the Twenty-Third International Joint Conference on Artificial Intelligence. Pages 817-822.

© 2013 International Joint Conferences on Artificial Intelligence

Abstract

Wastl introduced for first time a tableaux-like method based on an inference system for deriving all minimal keys from a relational schema. He introduced two inference rules and built an automated method over them.In this work we tackle the key finding problem with a tableaux method, but we will use two inference rules inspired by the Simplification Logic for Functional Dependencies. Wastl's method requires the input to be a set of functional dependencies with atomic right hand sides. Therefore, it is necessary to apply fragmentation rule with the consequent increasing of the input.The main novelty of our rules is that they deal with generalized formulas, avoiding the fragmentation needed in the former tableaux. Finally we illustrate the advantages of our new tableaux method with an experiment.

  1. W. Armstrong, Dependency structures of data base rela- tionships, in: IFIP Congress, 1974, pp. 580-583.
  2. E. F. Codd, A relational model of data for large shared data banks, Commun. ACM, 26 (1): 64-69, 1983.
  3. R. Elmasri, S. Navathe, Fundamentals of Database Sys- tems, 6th ed. Addison-Wesley, 2011.
  4. R. Fadous, J. Forsyth, Finding candidate keys for rela- tional data bases. SIGMOD international conference on Management of data, ACM, 1975, pp. 203-210.
  5. C. L. Lucchesi, S. L. Osborn, Candidate Keys for Re- lations, in: Journal of Computer and System Sciences (JCSS) 17(2):270 279, 1978.
  6. A. Mora, P. Cordero, M. Enciso, I. Fortes, G. Aguilera, Closure via functional dependence simplification, Inter- national Journal of Computer Mathematics. Volume 89, Issue 4, March 2012, pages 510-526 (2012).
  7. A. Mora, I. Pérez de Guzmán, M. Enciso, P. Cordero, Ideal non-deterministic operators as a formal framework to reduce the key finding problem, International Journal of Computer Mathematics 88 (2011) 1860-1868.
  8. H. Saiedian, T. Spencer, An efficient algorithm to com- pute the candidate keys of a relational database schema, The Computer Journal 39 (2) (1996) 124-132.
  9. Y. Sismanis, P. Brown, P. J. Haas, B. Reinwald, GOR- DIAN: efficient and scalable discovery of composite keys. Conf. on Very large databases, 2006, pp. 691-702.
  10. R. Wastl, Linear derivations for keys of a database re- lation schema, Journal of Universal Computer Science 4 (12) (1998) 883-897.
  11. C. T. Yu, D. T. Johnson, On the complexity of finding the set of candidate keys for a given set of functional dependencies, Inform. Process. Letters (1976) 100-101.
  12. Y. Zhang, Determining all candidate keys based on kar- naugh map. IEEE International Conference on Informa- tion Management, Innovation Management and Indus- trial Engineering -Volume 04, 2009, pp. 226-229.

References were extracted automatically from the PDF and may contain errors.

Welcome Future Conferences AI Journal Division IJCAI Proceedings About IJCAI IJCAI Awards