Review - Hypothetical Datalog: Complexity and Expressibility.
Victor Vianu:
Review - Hypothetical Datalog: Complexity and Expressibility.
ACM SIGMOD Digital Review 2: (2000) BibTeX
Review
This paper introduces an extension of Logic Programming
which integrates queries and updates. The proposed language,
"Hypothetical Datalog", provides an elegant tool for certain types of reasoning encountered in many applications, such as
encountered in many applications, such as legal expert systems.
Hypothetical reasoning allows capturing statements such as
the following, from the British Nationality Act:
"You are eligible for citizenship if your father would be eligible if he were
still alive".
Such statements are hard to capture with traditional tools; indeed, the semantics
and proof theory of Hypothetical Datalog are based on intuitionistic logic.
The resulting language provides new features which are very appealing
in many applications. Moreover, perhaps surprisingly, Hypothetical Datalog
is particularly well-behaved with respect to expressibility:
natural syntactic restrictions of the language express
the queries of data complexity EXPTIME, PSPACE, and each level of the
polynomial hierarchy.
These results involve particularly elegant and insightful simulations.
Copyright © 2000 by the author(s).
Review published with permission.
References
- [1]
- Anthony J. Bonner:
Hypothetical Datalog: Complexity and Expressibility.
Theor. Comput. Sci. 76(1): 3-51(1990) BibTeX
BibTeX
Digital Review - DBLP:
[Home | Search: Author, Title | Conferences | Journals]
Digital Review: Copyright © by ACM (info@acm.org),
DBLP: Copyright © by Michael Ley (ley@uni-trier.de), last change: Sat May 16 23:57:29 2009
