Paper Info
Title
New type of coding problem motivated by database theory
Abstract
The present paper is intended to survey the interaction between relational database theory and coding theory. In particular it is shown how an extremal problem for relational databases gives rise to a new type of coding problem. The former concerns minimal representation of branching dependencies that can be considered as a data mining type question. The extremal configurations involve d-distance sets in the space of disjoint pairs of k-element subsets of an n-element set X. Let X be an n-element finite set, 0 k n/2 an integer. Suppose that {A1, B1} and {A2, B2} are pairs of disjoint k-element subsets of X (that is, |A1| = |B1| = |A2| = |B2| = k, A1 ∩ B1 = 0, A2 ∩ B2 = 0). Define the distance of these pairs by d({A1, B1}, {A2, B2}) = min{|A1 - A2| + |B1 - B2|, |A1 - B2| + |B1 - A2|}.
Year
DOI
Venue
2004
10.1016/j.dam.2004.03.004
Discrete Applied Mathematics
Keywords
Field
DocType
database theory,new type,d-distance set,disjoint k-element subsets,extremal configuration,data mining type question,disjoint pair,k-element subsets,coding problem,relational databases,relational database theory,extremal problem,n-element finite set,coding theory,relational database,code,data mining
Integer,Discrete mathematics,Combinatorics,Finite set,Disjoint sets,Relational database,Coding (social sciences),Coding theory,Data type,Database theory,Mathematics
Journal
Volume
Issue
ISSN
144
1-2
Discrete Applied Mathematics
Citations 
PageRank 
References 
4
0.42
16
Authors
2
Name
Order
Citations
PageRank
Gyula O. H. Katona126466.44
Attila Sali216624.30