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. |
Year | DOI | Venue |
---|---|---|
2011 | 10.1016/j.ipl.2011.07.007 | Inf. Process. Lett. |
Keywords | Field | DocType |
functional dependency,multivalued dependency,relational databases,negative result,propositional logic,multivalued formula,horn formula,exact model,data dependency,membership query,equivalence query,databases,multivalued dependencies,relational database | Query learning,Discrete mathematics,Multivalued dependency,Relational database,Propositional calculus,Functional dependency,Theoretical computer science,Equivalence (measure theory),Dependency theory (database theory),Propositional variable,Mathematics | Journal |
Volume | Issue | ISSN |
111 | 19 | 0020-0190 |
Citations | PageRank | References |
4 | 0.45 | 7 |
Authors | ||
2 |
Name | Order | Citations | PageRank |
---|---|---|---|
Víctor Lavín Puente | 1 | 16 | 2.20 |
Montserrat Hermo | 2 | 55 | 10.77 |