Tech Report CS-91-39
A Closed-Form Evaluation for Datalog Queries with Integer-Order Constraints
Peter Z. Revesz
May 1991
Abstract:
We provide a generalization of Datalog based on generalizing databases with the addition of integer-order constraints to relational tuples. For Datalog queries with integer-order constraints we show that there is a closed-form evaluation. We also show that the tuple recognition problem can be done in PTIME in the size of the (generalized) database, assuming that the size of the constants in the query is logarithmic in the size of the database. Note that the absence of negation is critical. Datalog queries with integer-order constraints can express any Turing-computable function.(complete text in pdf)
| Page Owner: John Bazik | Last Modified: Fri Feb 9 17:44:33 2007 |