Reasoning with Examples: Propositional Formulae and Database Dependencies

DSpace/Manakin Repository

Reasoning with Examples: Propositional Formulae and Database Dependencies

Citable link to this page

 

 
Title: Reasoning with Examples: Propositional Formulae and Database Dependencies
Author: Khardon, Roni; Mannila, Heikki; Roth, Dan

Note: Order does not necessarily reflect citation order of authors.

Citation: Khardon, Roni, Heikki Mannila, and Dan Roth. 1995. Reasoning with Examples: Propositional Formulae and Database Dependencies. Harvard Computer Science Group Technical Report TR-15-95.
Full Text & Related Files:
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 necessarily give the correct results. However, under certain conditions example-based deduction can be used to obtain a correct and complete inference procedure. This is the case for Boolean formulae (reasoning with models) and for certain types of database integrity constraints (the use of Armstrong relations). We show that these approaches are closely related, and use the relationship to prove new results about the existence and sizes of Armstrong relations for Boolean dependencies. Further, we study the problem of translating between different representations of relational databases, in particular we consider Armstrong relations and Boolean dependencies, and prove some positive results in that context. Finally, we discuss the close relations between the questions of finding keys in relational databases and that of finding abductive explanations.
Terms of Use: This article is made available under the terms and conditions applicable to Other Posted Material, as set forth at http://nrs.harvard.edu/urn-3:HUL.InstRepos:dash.current.terms-of-use#LAA
Citable link to this page: http://nrs.harvard.edu/urn-3:HUL.InstRepos:25620470
Downloads of this work:

Show full Dublin Core record

This item appears in the following Collection(s)

 
 

Search DASH


Advanced Search
 
 

Submitters