Reasoning with examples: propositional formulae and database dependencies

Citation
R. Khardon et al., Reasoning with examples: propositional formulae and database dependencies, ACT INFORM, 36(4), 1999, pp. 267-286
Citations number
19
Categorie Soggetti
Information Tecnology & Communication Systems
Journal title
ACTA INFORMATICA
ISSN journal
00015903 → ACNP
Volume
36
Issue
4
Year of publication
1999
Pages
267 - 286
Database
ISI
SICI code
0001-5903(199907)36:4<267:RWEPFA>2.0.ZU;2-H
Abstract
For humans, looking at how concrete examples behave is an intuitive way of deriving conclusions. The drawback with this method is that it does not nec essarily give the correct results. However, under certain conditions exampl e-based deduction can be used to obtain a correct and complete inference pr ocedure. This is the case for Boolean formulae (reasoning with models) and for certain types of database integrity constraints (the use of Armstrong r elations). We show that these approaches are closely related, and use the r elationship to prove new results about the existence and size of Armstrong relations for Boolean dependencies. Furthermore, we exhibit close relations between the questions of finding keys in relational databases and that of finding abductive explanations. Further applications of the correspondence between these two approaches are also discussed.