Gyula O.H. Katona ; Krisztián Tichler - An extremal problem on trees and database theory

dmtcs:3461 - Discrete Mathematics & Theoretical Computer Science, January 1, 2005, DMTCS Proceedings vol. AE, European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05) - https://doi.org/10.46298/dmtcs.3461
An extremal problem on trees and database theory

Authors: Gyula O.H. Katona 1; Krisztián Tichler 2

  • 1 Alfréd Rényi Institute of Mathematics
  • 2 Technical University of Berlin / Technische Universität Berlin

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^{n(1-c\cdot \log \log n / \log n)}$ rows.

https://doi.org/10.46298/dmtcs.3461
Source: HAL:hal-01184450v1
Volume: DMTCS Proceedings vol. AE, European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05)
Section: Proceedings
Published on: January 1, 2005
Imported on: May 10, 2017
Keywords: relational database,minimum matrix representation,extremal problems,labelled directed tree,[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM],[MATH.MATH-CO] Mathematics [math]/Combinatorics [math.CO]

Linked publications - datasets - softwares

Source : ScholeXplorer IsRelatedTo DOI 10.1023/a:1026162114022
  • 10.1023/a:1026162114022
Extremal Theorems for Databases

Share and export

Consultation statistics

This page has been seen 139 times.
This article's PDF has been downloaded 291 times.