A time bound on the materialization of some recursively defined views
type: Item
instance of: scholarly article
title: A time bound on the materialization of some recursively defined views
zbMATH Open document ID: 0624.68095
DOI: 10.1007/BF01840452
author: Yannis E. Ioannidis
published in: Algorithmica
publication date: 1986-01-01T00:00:00Z
review text: 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)].
Mathematics Subject Classification ID: 68P20
Mathematics Subject Classification ID: 68P05
Mathematics Subject Classification ID: 68T15
Mathematics Subject Classification ID: 03D99
zbMATH DE Number: 4014082
zbMATH Keywords: recursively defined relations
zbMATH Keywords: uniformly bounded recursion
zbMATH Keywords: query processing
zbMATH Keywords: deductive databases
zbMATH Keywords: Horn clauses
describes a project that uses: INGRES
MaRDI profile type: Publication
cites work: Equivalences among Relational Expressions
cites work: Q3097395
cites work: Q3848243
cites work: A relational model of data for large shared data banks
cites work: Q4052071
cites work: Q3340205
cites work: On compiling queries in recursive first-order databases
cites work: Q3915990
cites work: On recursive axioms in deductive databases
cites work: Equivalences Among Relational Expressions with the Union and Difference Operators
description: scientific article; zbMATH DE number 4014082