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)

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: angol
DOI: https://doi.org/10.14232/actacyb.20.2.2011.5
Uncontrolled Keywords: Természettudomány, Informatika
Additional Information: Bibliogr.: p. 326-329.; Abstract
Date Deposited: 2016. Oct. 15. 12:24
Last Modified: 2018. Jun. 05. 14:22
URI: http://acta.bibl.u-szeged.hu/id/eprint/12912

Actions (login required)

View Item View Item