Change search
ReferencesLink to record
Permanent link

Direct link
Self-Correlation and Maximum Independence in Finite Relations
KTH, School of Computer Science and Communication (CSC).ORCID iD: 0000-0002-0074-8786
2015 (English)In: Electronic Proceedings in Theoretical Computer Science, ISSN 2075-2180, E-ISSN 2075-2180, no 191, 60-74 p.Article in journal (Refereed) PublishedText
Abstract [en]

We consider relations with no order on their attributes as in Database Theory. An independent partition of the set of attributes S of a finite relation R is any partition (sic) of S such that the join of the projections of R over the elements of (sic) yields R. Identifying independent partitions has many applications and corresponds conceptually to revealing orthogonality between sets of dimensions in multidimensional point spaces. A subset of S is termed self-correlated if there is a value of each of its attributes such that no tuple of R contains all those values. This paper uncovers a connection between independence and self-correlation, showing that the maximum independent partition is the least fixed point of a certain inflationary transformer alpha that operates on the finite lattice of partitions of S. alpha is defined via the minimal self-correlated subsets of S. We use some additional properties of alpha to show the said fixed point is still the limit of the standard approximation sequence, just as in Kleene's well-known fixed point theorem for continuous functions.

Place, publisher, year, edition, pages
2015. no 191, 60-74 p.
National Category
Computer Science
URN: urn:nbn:se:kth:diva-181011DOI: 10.4204/EPTCS.191.7ISI: 000367340500006OAI: diva2:897765

QC 20160126

Available from: 2016-01-26 Created: 2016-01-26 Last updated: 2016-01-26Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full text

Search in DiVA

By author/editor
Gurov, Dilian
By organisation
School of Computer Science and Communication (CSC)
In the same journal
Electronic Proceedings in Theoretical Computer Science
Computer Science

Search outside of DiVA

GoogleGoogle Scholar
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Altmetric score

Total: 51 hits
ReferencesLink to record
Permanent link

Direct link