Advertisement
Published in:
2012 | OriginalPaper | Chapter
Encoding Databases Satisfying a Given Set of Dependencies
Authors : Gyula O. H. Katona, Krisztián Tichler
Published in: Foundations of Information and Knowledge Systems
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
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.