A closed-form evaluation for Datalog queries with integer (gap)-order constraints (Q688670): Difference between revisions

We provide a generalization of Datalog based on generalizing databases by adding integer order constraints to relational tuples. For Datalog queries with integer (gap)-order constraints (denoted as Datalog\(^{<Z})\), 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 in critical, Datalog\(^ \neg\) queries with integer order constraints can express any Turing-computable function.