A time bound on the materialization of some recursively defined views (Q578941)

An important problem concerning query processing in deductive databases is how to detect the point at which further recursive processing gives no more answers to a given query. There are some cases where a termination condition exists, which is independent of the particular instance of the database. In the paper a class of simple Horn clauses is defined; necessary and sufficient conditions are given for a simple recursive Horn clause to be uniformly bounded, i.e. equivalent to a finite set of nonrecursive Horn clauses (its expansions). A weighted graph is constructed for a simple Horn clause; it is proved that the uniform boundedness of the clause is equivalent to the absence of cycles of nonzero weight in the corresponding graph. Large parts of the paper were presented to the VLDB'85 conference [\textit{Y. E. Ioannidis}, A time bound on the materialization of some recursively defined views, Proc. VLDB'85, Stockholm (\textit{A. Pirotte} and \textit{Y. Vassiliou} (eds.)), 219-226 (1985)].