Negative results on learning multivalued dependencies with queries

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.

► We study multivalued formulas and multivalued dependencies in the model of learning with queries. ► We prove that none of these classes are learnable with only membership queries. ► We also prove that they cannot be learned with equivalence queries alone.