REAL

On the distance of databases

Katona, Gyula and Sali, Attila (2012) On the distance of databases. ANNALS OF MATHEMATICS AND ARTIFICIAL INTELLIGENCE, 65 (2-3). pp. 199-216. ISSN 1012-2443

[img] Text
On the distance of databases.pdf
Restricted to Repository staff only

Download (379kB) | Request a copy

Abstract

In the present paper a distance concept of databases is investigated. Two database instances are of distance 0, if they have the same number of attributes and satisfy exactly the same set of functional dependencies. This naturally leads to the poset of closures as a model of changing database. The distance of two databases (closures) is defined to be the distance of the two closures in the Hasse diagram of that poset. We determine the diameter of the poset and show that the distance of two closures is equal to the natural lower bound, that is to the size of the symmetric difference of the collections of closed sets. We also investigate the diameter of the set of databases with a given system of keys. Sharp upper bounds are given in the case when the minimal keys are 2 (or r)-element sets. © 2012 Springer Science+Business Media B.V.

Item Type: Article
Uncontrolled Keywords: poset; KEYS; Hasse diagram; Distance of databases; Closures; Antikeys
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
SWORD Depositor: MTMT SWORD
Depositing User: MTMT SWORD
Date Deposited: 10 Dec 2013 17:16
Last Modified: 10 Dec 2013 17:16
URI: http://real.mtak.hu/id/eprint/7993

Actions (login required)

Edit Item Edit Item