Negative results on learning multivalued dependencies with queries

作者：Lavin Puente Victor; Hermo Montserrat

来源：Information Processing Letters, 2011, 111(19): 968-972.

DOI：10.1016/j.ipl.2011.07.007

• Query learning
• Databases
• Propositional formulas
• Multivalued dependencies

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.

• 出版日期2011-10-15