An extremal problem on trees and database theoryReportar como inadecuado

An extremal problem on trees and database theory - Descarga este documento en PDF. Documentación en PDF para descargar gratis. Disponible también para leer online.

1 Alfréd Rényi Institute of Mathematics 2 TUB - Technische Universität Berlin Berlin

Abstract : We consider an extremal problem on labelled directed trees and applications to database theory. Among others, we will show explicit keysystems on an underlying set of size $n$, that cannot be represented by a database of less than $2^{n1-c\cdot \log \log n - \log n}$ rows.

Keywords : relational database minimum matrix representation extremal problems labelled directed tree

Autor: Gyula O.H. Katona - Krisztián Tichler -



Documentos relacionados