Michael Schrefl, Markus Stumptner,
"On the Formal Properties of Transitive Inheritance in Databases"
, in Information Sciences, Vol. 66, Nummer 1-2, Elsevier Science B.V. (North-Holland), Amsterdam, Seite(n) 63-90, 1992, ISSN: 0020-0255
On the Formal Properties of Transitive Inheritance in Databases
Sprache des Titels:
The paper investigates transitive inheritance relationships, represented formally by transitive inheritance dependencies (TIDs), between (sequences of) attributes of a relational scheme, e.g., part and subpart. The study of TIDs reveals a simple complete axiomatization for the implication problem, which is shown to be NP-complete. The interaction of TIDs with functional dependencies (FDs) is investigated, leading to the following main results: TIDs and FDs considered together imply new TIDs, but no new FDs. Furthermore, only longer TIDs, i.e., TIDs that contain more attributes, but not shorter ones, are implied. The membership problem for TIDs and FDs is decidable although the implication problem for FDs and TIDs together has no k-ary axiomatization. Sound and complete decision procedures are given for the membership problem for TIDs alone as well as for TIDs and FDs.
Sprache der Kurzfassung:
Elsevier Science B.V. (North-Holland)
Anzahl der Seiten:
Notiz zur Publikation:
If you are interested in th paper, you may receive a copy (PS or PDF) by sending an e-mail to our office (firstname.lastname@example.org). Please include the paper-no. (Schr92a) and agree to use the paper for scientific purposes and private use only!