Weak functional dependencies on trees with restructuring

Sali Attila and Schewe Klaus-Dieter: Weak functional dependencies on trees with restructuring. In: Acta cybernetica, (20) 2. pp. 285-329. (2011)

[thumbnail of actacyb_20_2_2011_5.pdf]
Cikk, tanulmány, mű

Download (527kB) | Preview


We present an axiomatisation for weak functional dependencies, i.e. disjunctions of functional dependencies, in the presence of several constructors for complex values. The investigated constructors capture records, sets, multisets, lists, disjoint union and optionality, i.e. the complex values are indeed trees. The constructors cover the gist of all complex value data models including object oriented databases and XML. Functional and weak functional dependencies are expressed on a lattice of subattributes, which even carries the structure of a Brouwer algebra as long as the union-constructor is absent. Its presence, however, complicates all results and proofs significantly. The reason for this is that the union-constructor causes non-trivial restructuring rules to hold. In particular, if either the set- or the the union-constructor is absent, a subset of the rules is complete for the implication of ordinary functional dependencies, while in the general case no finite axiomatisation for functional dependencies exists.

Item Type: Article
Heading title: Regular papers
Journal or Publication Title: Acta cybernetica
Date: 2011
Volume: 20
Number: 2
ISSN: 0324-721X
Page Range: pp. 285-329
Language: English
Place of Publication: Szeged
Related URLs: http://acta.bibl.u-szeged.hu/38532/
DOI: 10.14232/actacyb.20.2.2011.5
Uncontrolled Keywords: Számítástechnika, Kibernetika
Additional Information: Bibliogr.: p. 326-329. ; összefoglalás angol nyelven
Subjects: 01. Natural sciences
01. Natural sciences > 01.02. Computer and information sciences
Date Deposited: 2016. Oct. 15. 12:24
Last Modified: 2022. Jun. 17. 14:09
URI: http://acta.bibl.u-szeged.hu/id/eprint/12912

Actions (login required)

View Item View Item