AVERAGE-CASE COMPLEXITY FOR THE EXECUTION OF RECURSIVE DEFINITIONS ONRELATIONAL DATABASES

The execution costs of various types of database queries, expressed in terms of linear recusive definitions, are evaluated for two common qu ery evaluation algorithms in the case where the database relations are represented by forests of labelled oriented trees. In a first stage, the execution costs are computed for a given forest. A key issue in th is computation is the partition of the set of nodes in the forest into equivalence classes, the properties of which are explored. Moreover, the representation adopted is conceptually simple and provides additio nal results which are of interest by themselves. In a second stage, th e averages of these costs, computed over all databases representable b y forests with a given number of nodes, are also evaluated. Finally, t he execution cost of the considered database queries is computed for t he case where the underlined database relations ate modelled as Hamilt onian digraphs.