Inferring Minimal Functional Dependencies in Horn and q-Horn Theories |
| |
Authors: | Toshihide Ibaraki Alexander Kogan Kazuhisa Makino |
| |
Affiliation: | (1) Department of Applied Mathematics and Physics, Graduate School of Informatics, Kyoto University, Kyoto, Japan, 606-8501;(2) Department of Accounting and Information Systems, Rutgers Business School, Rutgers University, Newark, NJ, 07102;(3) RUTCOR, Rutgers University, 640 Bartholomew Road, Piscataway, NJ 08854-8003, USA;(4) Division of Systems Science, Graduate School of Engineering Science, Osaka University, Toyonaka, Osaka, Japan, 560-8531 |
| |
Abstract: | In this paper, we study various problems related to the inference of minimal functional dependencies in Horn and q-Horn theories. We show that if a Horn theory is represented by a Horn CNF, then there exists an incrementally polynomial algorithm for inferring all minimal functional dependencies. On the other hand, if a Horn theory is represented as the Horn envelope of a given set of models, then there exists a polynomial total time algorithm for this inference problem if and only if there exists such an algorithm for dualizing a positive CNF. Finally, we generalize our results to the case of q-Horn theories, and show that all the considered problems can be reduced in polynomial time to the corresponding problems for Horn theories. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|