Paper Info
Title
Encoding databases satisfying a given set of dependencies
Abstract
Consider a relation schema with a set of dependency constraints. A fundamental question is what is the minimum space where the possible instances of the schema can be "stored". We study the following model. Encode the instances by giving a function which maps the set of possible instances into the set of words of a given length over the binary alphabet in a decodable way. The problem is to find the minimum length needed. This minimum is called the information content of the database. We investigate several cases where the set of dependency constraints consist of relatively simple sets of functional or multivalued dependencies. We also consider the following natural extension. Is it possible to encode the instances such a way that small changes in the instance cause a small change in the code.
Year
DOI
Venue
2012
10.1007/978-3-642-28472-4_12
FoIKS
Keywords
Field
DocType
multivalued dependency,following natural extension,relation schema,encoding databases,minimum length,dependency constraint,possible instance,following model,minimum space,small change,simple set,relational database,functional dependency,coding
ENCODE,Multivalued dependency,Fourth normal form,Relational database,Computer science,Join dependency,Algorithm,Theoretical computer science,Functional dependency,Database,Dependency theory (database theory),Encoding (memory)
Conference
Citations 
PageRank 
References 
0
0.34
10
Authors
2
Name
Order
Citations
PageRank
Gyula O. H. Katona126466.44
Krisztián Tichler2182.45