Encoding databases satisfying a given set of dependencies

Katona, Gyula and Tichler, K. (2012) Encoding databases satisfying a given set of dependencies. LECTURE NOTES IN COMPUTER SCIENCE, 7153. pp. 203-223. ISSN 0302-9743

Encoding databases satisfying a given set of dependencies.pdf

Download (337kB) | Preview


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. © 2012 Springer-Verlag.

Item Type: Article
Additional Information: 7th International Symposium on Foundations of Information and Knowledge Systems (FoIKS), 5-9 March 2012, Kiel
Uncontrolled Keywords: Encoding (symbols); Database systems; Natural extension; Information contents; Dependency constraints; Binary alphabets; relational database; multivalued dependency; functional dependency; coding
Subjects: Q Science / természettudomány > QA Mathematics / matematika
Q Science / természettudomány > QA Mathematics / matematika > QA75 Electronic computers. Computer science / számítástechnika, számítógéptudomány
Depositing User: MTMT SWORD
Date Deposited: 11 Dec 2013 09:43
Last Modified: 11 Dec 2013 10:13

Actions (login required)

Edit Item Edit Item