Negative results on learning multivalued dependencies with queries |
| |
Authors: | Víctor Lavín Puente Montserrat Hermo |
| |
Affiliation: | a Dpto. Sistemas Informáticos y Computación, Universidad Complutense, E-28040 Madrid, Spain b Dpto. Lenguajes y Sistemas Informáticos, P.O. Box 649, E-20080 San Sebastián, Spain |
| |
Abstract: | Data dependencies are useful to design relational databases. There is a strong connection between dependencies and some fragments of the propositional logic. In particular, functional dependencies are closely related to Horn formulas. Also, multivalued dependencies are characterized in terms of multivalued formulas. It is known that both Horn formulas and sets of functional dependencies are learnable in the exact model of learning with queries. Here we proof that neither multivalued formulas nor multivalued dependencies can be learned using only membership queries or only equivalence queries. |
| |
Keywords: | Query learning Databases Propositional formulas Multivalued dependencies |
本文献已被 ScienceDirect 等数据库收录! |