Average-case complexity for the execution of recursive definitions on relational databases (paper no 50-95 accepted for publication in ACTA INFORMATICA) (Q1386412): Difference between revisions
From MaRDI portal
Created a new Item |
Set OpenAlex properties. |
||
(4 intermediate revisions by 3 users not shown) | |||
Property / author | |||
Property / author: Wenceslas Fernandez de la Vega / rank | |||
Property / author | |||
Property / author: Wenceslas Fernandez de la Vega / rank | |||
Normal rank | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1007/s002360050119 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2024436296 / rank | |||
Normal rank | |||
links / mardi / name | links / mardi / name | ||
Latest revision as of 01:19, 20 March 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Average-case complexity for the execution of recursive definitions on relational databases (paper no 50-95 accepted for publication in ACTA INFORMATICA) |
scientific article |
Statements
Average-case complexity for the execution of recursive definitions on relational databases (paper no 50-95 accepted for publication in ACTA INFORMATICA) (English)
0 references
10 August 1998
0 references
The execution costs of various types of database queries, expressed in terms of linear recursive definitions, are evaluated for two common query 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 first for a given forest. A key issue in this 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 additional results which are of interest by themselves. In a second stage, the averages of these costs, computed over all databases representable by forests with a given number of nodes, are also evaluated. Finally, the execution cost of the considered database queries is computed for the case where the underlined database relations are modelled as Hamiltonian acyclic digraphs.
0 references
database queries
0 references