Temporal Stratification Tests for Linear and Branching-Time Deductive Databases
Panos Rondogiannis, Christos Nomikos, Manolis Gergatsoulis
Abstract:
We consider the problem of extending temporal deductive databases with stratified negation.
We argue that the classical stratification test for deductive databases is too restrictive
when one shifts attention to the temporal case. Moreover, as we demonstrate, the (more general)
local stratification approach is impractical: detecting whether a temporal deductive database is locally
stratified is shown to be co-NP hard (even if one restricts attention to programs that only use one
predicate symbol and two constants). For these reasons we define temporal stratification,
an intermediate notion between stratification and local stratification. We demonstrate that for the temporal
deductive databases we consider, temporal stratification coincides with local stratification in certain important
cases in which the latter is polynomial-time decidable. We then develop two algorithms for detecting temporal
stratification. The first algorithm applies to linear-time temporal deductive databases and it is efficient and more
general than existing approaches; however, the algorithm sacrifices completeness for efficiency since
it does not cover the whole class of temporally stratified programs. The second algorithm applies to
branching-time temporal deductive databases (which include as a special case the linear-time ones).
This algorithm is more expensive from a computational point of view, but it covers the whole class of
temporally stratified programs. We discuss the relative merits of the two algorithms and compare them
with other existing approaches.
Keywords:
Temporal Deductive Databases, Temporal Logic Programming, Stratified Negation.