Self-Correlation and Maximum Independence in Finite Relations
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 X of S such that the join of the projections of R over the elements of X yields R. Identifying independent partitions has many a...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Open Publishing Association
2015-09-01
|
| Series: | Electronic Proceedings in Theoretical Computer Science |
| Online Access: | http://arxiv.org/pdf/1509.03016v1 |
| _version_ | 1811307135729926144 |
|---|---|
| author | Dilian Gurov Minko Markov |
| author_facet | Dilian Gurov Minko Markov |
| author_sort | Dilian Gurov |
| collection | DOAJ |
| description | 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 X of S such that the join of the projections of R over the elements of X 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. |
| first_indexed | 2024-04-13T08:59:15Z |
| format | Article |
| id | doaj.art-c0c82cfcc6344ab2beadc37b22e198b1 |
| institution | Directory Open Access Journal |
| issn | 2075-2180 |
| language | English |
| last_indexed | 2024-04-13T08:59:15Z |
| publishDate | 2015-09-01 |
| publisher | Open Publishing Association |
| record_format | Article |
| series | Electronic Proceedings in Theoretical Computer Science |
| spelling | doaj.art-c0c82cfcc6344ab2beadc37b22e198b12022-12-22T02:53:12ZengOpen Publishing AssociationElectronic Proceedings in Theoretical Computer Science2075-21802015-09-01191Proc. FICS 2015607410.4204/EPTCS.191.7:2Self-Correlation and Maximum Independence in Finite RelationsDilian Gurov0Minko Markov1 KTH Royal Institute of Technology, Stockholm, Sweden St. Kliment Ohridski University of Sofia, Sofia, Bulgaria 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 X of S such that the join of the projections of R over the elements of X 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.http://arxiv.org/pdf/1509.03016v1 |
| spellingShingle | Dilian Gurov Minko Markov Self-Correlation and Maximum Independence in Finite Relations Electronic Proceedings in Theoretical Computer Science |
| title | Self-Correlation and Maximum Independence in Finite Relations |
| title_full | Self-Correlation and Maximum Independence in Finite Relations |
| title_fullStr | Self-Correlation and Maximum Independence in Finite Relations |
| title_full_unstemmed | Self-Correlation and Maximum Independence in Finite Relations |
| title_short | Self-Correlation and Maximum Independence in Finite Relations |
| title_sort | self correlation and maximum independence in finite relations |
| url | http://arxiv.org/pdf/1509.03016v1 |
| work_keys_str_mv | AT diliangurov selfcorrelationandmaximumindependenceinfiniterelations AT minkomarkov selfcorrelationandmaximumindependenceinfiniterelations |