Hubungan. Bagian I

Teori formal pemodelan menggunakan relasi aljabar, termasuk di dalamnya tanda tangan model struktur aljabar, yang mendeskripsikan objek fisik, teknis dan informasional yang nyata, proses-proses fungsinya. Di antara yang terakhir saya sertakan, misalnya, database (database relasional (RDB)). Saya menganggap bidang pengambilan keputusan menjadi tidak kalah pentingnya, yang terdiri dari dua statistik utama dan aljabar, yang seluruhnya didasarkan pada teori hubungan. Tingkat pendidikan spesialis dalam teori ini mendekati nol.



Buka buku teks tentang spesialisasi dan di sana Anda akan melihat, paling banter, tentang kesetaraan, yang ditafsirkan oleh penulis dengan cara yang sangat aneh. Saya bertanya kepada salah satu DTN yang sudah dipertahankan: Apakah Anda mempertimbangkan hubungan kesetaraan dengan tidak menunjukkan pembawa hubungan tersebut, atau pun hubungan tertentu, bagaimana tampilannya dalam catatan Anda? Jawaban: seperti apa - biasanya. Ternyata dia memiliki gagasan yang sangat kabur tentang semua ini.



Saya merasa sulit untuk menyebutkan publikasi tentang desain ReDB, kecuali untuk artikel asing. Pada tahun 90-an, dia adalah seorang lawan, menulis review dari tesis, yang dianggap database hirarkis, jaringan, dan relasional. Tapi setahun sekali, satu setengah tahun yang lalu, pekerjaan kembali untuk ditinjau, penulis sudah hanya menulis tentang DB, tentang normalisasi hubungan DB, tetapi tidak menunjukkan kebaruan teoritis. Banyak universitas mengajarkan kursus tentang database, tetapi tidak tentang cara membuatnya, membuat DBMS, tetapi, sebagai aturan, tentang cara mengoperasikan database (asing) yang sudah jadi.



Putaran. staf tidak siap untuk mengajar spesialis TI untuk membuat DBMS domestik, OS, bahasa pemrograman, belum lagi LSI, VLSI, LSI kustom. Di sini, rupanya, kereta berangkat untuk waktu yang lama dan waktu yang lama. Maka dengan sia-sia ada pipi yang sombong (baca keangkuhan), hal ini terlihat dari komentar di publikasi orang lain, tunjukkan pada diri sendiri bahwa kamu bisa, dan jangan memanjakan diri dengan terjemahan yang tidak berguna dan re-song orang lain demi kebanggaan - "rating" dan "karma" Mempengaruhi tidak hanya kurangnya kreativitas, tetapi pendidikan dan pendidikan sederhana.



Domain kedua yang terkait erat dengan hubungan adalah pengambilan keputusan. Masing-masing dari kita selalu sibuk dengan ini. Kami tidak akan mengangkat jari tanpa keputusan sadar atau tidak sadar. Sedikit yang mengerti, bahkan sedikit yang menulis tentang solusi. Keputusan setiap pembuat keputusan (pengambil keputusan) didasarkan pada preferensi untuk alternatif. Dan model preferensi tepatnya adalah jenis hubungan ini, yang disebut "ruang hubungan preferensi". Tapi siapa yang mempelajarinya. Ketika saya datang ke "spesialis" dalam kaitannya dengan pertanyaan tentang jumlah hubungan masing-masing jenis, dia, tidak tahu jawabannya, "membunuh" dengan pertanyaan balasan, mengapa Anda membutuhkannya?

Konsep hubungan

Saya pikir istilah sikap sudah tidak asing lagi bagi setiap pembaca, tetapi menanyakan definisi akan sangat membingungkan. Ada banyak alasan untuk ini. Mereka paling sering pada guru yang, jika mereka menggunakan hubungan dalam proses pengajaran, tidak fokus pada istilah ini, tampaknya tidak mengutip contoh yang mudah diingat.



Dalam ingatan saya, ada beberapa contoh yang bisa diingat seumur hidup. Tentang pemetaan dan hubungan. Saya akan berbicara tentang pemetaan dulu. Ada dua ember cat. Di satu putih, di yang lain - hitam. Dan ada sekotak kubus (banyak). Tepinya memiliki angka timbul. Berapa banyak cara Anda bisa mewarnai wajah kubus dalam dua warna? Jawabannya tidak terduga - sebanyak 6-bit bilangan biner, atau 2 ⁶= 64. Izinkan saya menjelaskan lebih detail f: 2 → 6 2 objek ditampilkan di 6. Setiap baris tabel adalah tampilan diskrit dari fi.



Mari buat tabel dengan 6 kolom dan warnanya akan cocok dengan angka putih - nol, hitam - satu, dan permukaan kubus adalah kolom. Kita mulai dengan fakta bahwa semua 6 sisi berwarna putih - ini adalah vektor nol 6 dimensi. Baris kedua adalah satu segi hitam, yaitu bit paling tidak signifikan diisi dengan 1. dan seterusnya sampai bilangan biner 6-bit habis. Kami menempatkan kubus dalam baris panjang yang umum. Masing-masing tampaknya memiliki angka dari 0 hingga 63.



Sekarang tampilan dibalik. Satu pak lembaran kertas (banyak) dan 6 cat (spidol).

Tandai kedua sisi lembaran kertas dengan spidol dengan warna berbeda. Berapa lembar yang dibutuhkan. Jawaban f: 6 → 2 atau 6 ² = 36. Ini adalah pemetaan sewenang-wenang.



Mari beralih ke hubungan. Mari kita mulai dengan himpunan abstrak - pembawa relasi

= {a1, a2, a3, ..., an}.

Anda dapat membacanya di sini . Untuk pemahaman yang lebih baik, kami akan mengurangi set menjadi 3 elemen, yaitu A = {a1, a2, a3}. Sekarang kita melakukan perkalian Cartesian × = ² ,

× = {(a1, a1), (a1, a2), (a1, a3), (a2, a1), (a2, a2), (a2, a3) ), (a3, a1), (a3, a2), (a3, a3)}.



Kami mendapat 9 pasang elemen yang teratur dari A × A, dalam pasangan elemen pertama dari faktor pertama, yang kedua dari yang kedua. Sekarang mari kita coba mendapatkan semua himpunan bagian dari kotak A × A Cartesian. Pertama, contoh sederhana.



Contoh 1... Himpunan A = {a, b, c, d} dari 4 elemen diberikan. Tuliskan semua subsetnya. B (A) = {Ø}; {a}; {b}; {c}; {d}; {ab}; {ac}; {ad}; {bc}; {bd}; {cd}; { abc}; {abd}; {acd}; {bcd}; {abcd}; 2 ⁴ = 16 subset. Ini adalah Boolean B (A) dari himpunan A dan ini mencakup subset kosong.



Himpunan bagian akan berisi dari A × A sejumlah elemen (pasangan) yang berbeda: satu, dua, tiga, dan seterusnya hingga semua 9 pasangan, kami juga menyertakan himpunan kosong (Ø) dalam daftar ini. Ada berapa subset? Banyak, yaitu 2 ⁹ = 512 elemen.



Definisi . Setiap bagian dari produk Cartesian (kita memiliki kuadrat) dari suatu himpunan disebut relasi . Perhatikan bahwa pekerjaan menggunakan set yang sama. Jika himpunan berbeda, tidak ada hubungan, tetapi korespondensi...



Jika ini adalah perkalian Kartesius dari dua faktor, maka relasinya adalah biner , jika dari 3 internal, dari 4 adalah tetrar, dan dari n adalah n-ary. Arity adalah jumlah tempat dalam suatu relasi. Hubungan diberi nama huruf kapital R, H, P, S ... Mari kita pikirkan hubungan biner (BO), karena mereka memainkan peran yang sangat penting dalam teori hubungan. Sebenarnya semua yang lain dapat direduksi menjadi hubungan biner.



Simbol relasi ditempatkan di sebelah kiri elemen R (x, y) atau di antara mereka x R y; x, y є A.

Definisi Himpunan semua himpunan bagian dari himpunan A disebut Boolean. Boolean kami terdiri dari 2 ^{| A × A |} elemen, di sini | A × A | Apakah kardinalitas himpunan.



Hubungan dapat diatur dalam representasi yang berbeda melalui = {a1, a2, a3, a4}:

• pencacahan elemen; R1 = {(a1, a2), (a1, a3), (a2, a3) (a2, a4) (a3, a2) (a3, a4}
• biner n = vektor 16-bit; <0110001101010000>;
• matriks;

Gambar 1.2. a) 4 × 4 matriks relasi biner b) penomoran sel matriks



Di sini, nomor sel digunakan, diisi dengan yang ada di Gambar. 1b)

- Representasi vektor. Vektor biner untuk merepresentasikan relasi biner dibentuk dari elemen {0,1} sebagai berikut:



Contoh pengaturan hubungan dalam bentuk vektor yang dipertimbangkan akan terlihat seperti ini:





- Representasi grafik. Mari kita kaitkan elemen-elemen himpunan

A = {x1, x2, z3, ..., xn} dengan titik-titik pada bidang, yaitu, simpul dari grafik G = [Q, R].



Gambarkan busur dalam grafik dari (xi) ke (xj) jika dan hanya jika pasangan (xi, xj) є R (untuk i = j, busur (xi, xi) berubah menjadi lingkaran pada puncak (xi) Contoh (Gbr. 1a) representasi dari relasi biner A [4 × 4] dengan grafik ditunjukkan pada Gambar.2.2.



Gambar 2.2. Representasi relasi dengan graf berarah



Katalog relasi biner (n = 3)



Besar terlihat dari kejauhan. Untuk merasakan hubungan dan keragamannya, kekuatan yang saya miliki untuk secara manual membuat katalog hubungan biner melalui sekumpulan 3 elemen, yang mencakup semua (lebih dari 500 hubungan) hubungan. Setelah itu, datang atau pergi tentang hubungan.



Tentunya, katalog akan mencakup 2 ^{3 × 3} = 2 ⁹relasi, dan masing-masing akan dilengkapi dengan satu set properti yang melekat. Di bawah (Tabel 3) adalah daftar lengkap semua 512 relasi di atas himpunan A, | A | = 3, dari tiga elemen. Hasil penghitungan jumlah rasio (Tabel 2), yang diwakili oleh kombinasi jumlah sel dari Cartesian square 3 × 3, dari subclass yang berbeda untuk nilai berbeda dari kardinalitas himpunan pembawa (n = 3) juga diberikan. Untuk setiap hubungan, properti dasarnya dan jenisnya ditunjukkan (Tabel 3). Singkatan yang digunakan dalam katalog diungkapkan pada Tabel 2

Tabel 2. Karakteristik kuantitatif katalog untuk n yang berbeda





Lebih mudah menjelaskan esensi operasi dengan relasi dan tekniknya menggunakan contoh-contoh yang sangat sederhana dan dapat dimengerti untuk relasi biner. Operasi dapat melibatkan dua dan / atau lebih hubungan. Operasi yang dilakukan pada relasi individu adalah operasi unary. Misalnya, operasi pembalikan (memperoleh kebalikan) suatu relasi, mengambil komplemen, mempersempit (membatasi) relasi. Sebuah contoh akan menggambarkan bagaimana menggunakan katalog.



Contoh 2 . Pertimbangkan baris Npr = 14 dari tabel katalog. Ini memiliki bentuk



9 karakter pertama dari garis (di sebelah kanan persamaan) adalah vektor biner yang sesuai dengan kombinasi 9 hingga 2, yaitu, jumlah sel pertama (dihitung dari kiri ke kanan) adalah jumlah sel ke-5 dari matriks relasi biner, yaitu. elemen a1a1 = a2a2 = 1. Kombinasi ini memiliki nomor urut Ncc = 4 dan nomor melalui Npr = 14 dalam daftar semua relasi. Sisa baris ini berisi nol atau satu. Nol menunjukkan tidak adanya properti yang sesuai dengan nama kolom nol, dan satu menunjukkan adanya properti tersebut dalam relasi yang dipertimbangkan.

Sifat dan karakteristik kuantitatif dari hubungan

Mari kita pertimbangkan properti paling penting dari relasi, yang akan memungkinkan kita untuk lebih menyoroti jenis (kelas) relasi yang digunakan dalam database relasional dalam teori pilihan dan pengambilan keputusan serta aplikasi lainnya. Berikut ini, kami akan menunjukkan relasinya dengan simbol [R, Ω]. R adalah nama relasi, Ω adalah himpunan pembawa relasi.



1. Refleksivitas. Relasi [R, Ω] disebut refleksif jika setiap elemen himpunan berada dalam relasi R dengan dirinya sendiri (Gbr. 2.3). Grafik BO refleksif memiliki loop (busur) di semua simpul, dan matriks relasi berisi (E) unit diagonal utama.





Gambar 2.3. Sikap refleksif



2. Anti reflektif . Relasi [R, Ω] disebut antirefleksif jika tidak ada elemen himpunan dalam relasi R dengan dirinya sendiri (Gbr. 2.4). Hubungan anti reflektif disebut ketat.





Gambar 2.4. Sikap anti-



reflektif 3. Refleksivitas parsial. Relasi [R, Ω] disebut

refleksif sebagian jika satu atau lebih elemen dari himpunan tidak berada dalam relasi R dengan dirinya sendiri (Gbr. 2.5).





4. Simetri. Suatu relasi [R, Ω] disebut simetris jika, bersama-sama dengan pasangan terurut (x, y), relasi tersebut juga mengandung pasangan terurut (y, x) (Gbr. 2.6).





5. Antisimetri. Suatu relasi [R, Ω] disebut antisimetrik jika, jika, untuk setiap pasangan terurut (x, y) є R, pasangan terurut

(y, x) єR, hanya dalam kasus x = y. Untuk rasio seperti R∩R ^-1 ⊆ E (Gbr. 2.7).





6. Asimetri. Suatu relasi [R, Ω] disebut asimetris jika antirefleksif dan untuk setiap pasangan terurut (x, y) є R merupakan pasangan terurut (y, x) ∉ R, untuk relasi R ∩ R ^-1 = Ø (Gbr. 2.8).





7. Transitivitas. Relasi [R, Ω] disebut transitif jika, untuk setiap pasangan terurut (x, y), (y, z) є R, dalam relasi R ada pasangan terurut (x, z) є R atau jika R × R⊆R (Gbr. . 2.9).





8. Siklus. Suatu relasi [R, Ω] disebut siklik jika untuk elemennya {x1, x2, z3, ..., xn} terdapat himpunan bagian dari elemen {xi, xi + 1, ... xr, ..., xj, xi}, yang mana seseorang dapat menuliskan urutan xiRxi + 1R ... RxjRxi. Urutan seperti itu disebut siklus atau loop (Gambar 2.10).





9. Acyclicity. Hubungan di mana tidak ada kontur disebut asiklik. Untuk hubungan asiklik, hubungan R ^k ∩R = Ø untuk setiap k> 1 berlaku (Gbr. 2.11).







10. Kelengkapan (konektivitas). Relasi [R, Ω] disebut lengkap (terhubung) jika untuk dua elemen (y, z) є Ω salah satunya berhubungan dengan elemen lainnya (Gbr. 2.12). Linearitas. Hubungan linier adalah hubungan minimal lengkap.





Gambar 2.12. Relasi linier



Jadi, kita telah menetapkan bahwa relasi, sebagai objek matematika, memiliki properti tertentu, definisi yang diberikan sebelumnya. Di paragraf berikutnya, kami akan mempertimbangkan esensi dan manifestasi dari beberapa properti:

1. Refleksivitas x є A (xRx).
2. Antifleksibilitas x є A ¬ (xRx).
3. Simetri x, y є A (xRy → yRx).
4. Antisimetri (xRy & yRx → x = y).
5. Transitivitas; x, y, z є A (xRy & yRz → xRz).
6. Siklisitas; x, y є A; ...
7. Kelengkapan x, y є (xRy, yRx);
8. Konektivitas (x ≠ y → xRy, yRx).
9. Linearitas x, y є (xRy, yRx).

Analisis ruang hubungan adalah tugas teori yang kompleks dan, harus dicatat, masih jauh dari selesai. Hasil utama harus mencakup pemilihan subset relasi yang membentuk ruang relasi lengkap dengan semua konsekuensi selanjutnya.



Hubungan kuantitatif dari ruang diskrit semacam itu sangat menarik baik

secara teoritis maupun praktis. Beberapa aspek karakteristik kuantitatif yang terkait dengan sifat-sifat relasi dari berbagai tipe dibahas di bawah ini.

Operasi hubungan

Seperti kebanyakan sistem bilangan dengan relasi, operasi berikut dilakukan:

• unary;
• biner;
• n-ary.

Berikut adalah tabel penjumlahan dan perkalian Boolean ⊕ & dari dua variabel x1 dan x2, penjumlahan mod 2 dan penjumlahan biner:





Di atas, konsep relasi biner diperkenalkan, sebagai bagian dari pasangan terurut dari produk himpunan Cartesian, dan properti relasi juga dipertimbangkan. Selain itu, hubungan biner dan representasi matriks dari hubungan juga disebutkan. Sekarang mari kita pertimbangkan konsep relasi secara lebih rinci, sebagai tambahan, pertimbangkan operasi dasar dari relasi biner, yang paling penting dari himpunan mereka untuk relasi.



Bagi mereka, kondisi berikut harus dipenuhi:

• Aritas operand dalam operasi harus cocok;
• hasil operasi harus berupa relasi dengan arity yang sama.

Untuk relasi biner dan n-ary, berikut ini harus dipenuhi: area kedatangan operan pertama harus cocok dengan area asal dari operan kedua.



Operasi unary pada relasi



Pembalikan relasi . Kebalikan dari relasi R adalah rasio R ^-1 , yang ditentukan oleh kondisi xR ^-1 y <=> yRx. Lebih tepatnya, operasi ini harus disebut pseudo-inversion, karena p · p ^-1 ≠ E = Δ.



Biarkan relasi P ditulis dalam bentuk pencacahan pasangan terurut yang termasuk di dalamnya. Jika komponen-komponen tersebut saling dipertukarkan pada setiap pasangan, maka pasangan baru tersebut membentuk rasio P ^-1 , yang disebut inversi P.



Relasi terbalik dengan relasi P adalah relasi yang dibentuk oleh pasangan (ai aj) yang dengannya (aj ai) є P ^-1 . Untuk relasi dalam bentuk matriks, relasi invers diperoleh dengan transposisi matriks P.



9. Relasi rangkap (P ^d ) ke relasi P adalah relasi yang dibentuk oleh semua pasangan yang termasuk dalam relasi universal dan bukan milik relasi invers (selain invers):



P ^d = {(ai aj) | ((ai aj) єA × A) & (ai aj) ∉ P ^-1 )} = (A × A) \ P ^-1 .



Hubungan rangkap dan kebalikan dalam agregat berisi semua pasangan dari perkalian Kartesius A × A dan tidak memiliki pasangan yang sama, mereka, seperti hubungan P dan P membentuk partisi A × A





Perhatikan bahwa untuk setiap relasi P tidak terpenuhi P P = ^d .



Mempersempit (PA1). Relasi [R1, A1] disebut restriksi relasi [R, A] terhadap himpunan Ω1 jika Ω1⊆ Ω dan R1 = R∩Ω1 × Ω1. Rasio PA1 pada himpunan A1 ⊆ A adalah rasio PA1 pada himpunan A1, yang dibentuk oleh semua pasangan yang termasuk dalam relasi P dan sekaligus merupakan bagian dari perkalian Kartesius A1 × A1. Dengan kata lain, PA1 adalah perpotongan dari relasi P dan A1 × A1. Misalkan A1 = {a1, a3, a4}, maka untuk relasi P dan Q berbentuk matriks, relasi yang menyempit tersebut akan berbentuk:





Operasi Biner Operasi yang



membutuhkan setidaknya dua relasi adalah n-ary (n-ary). Hanya relasi dengan aritas yang sama yang dapat berpartisipasi dalam operasi tersebut. Contoh operasi tersebut: persimpangan, persatuan, perbedaan, perbedaan hubungan simetris, dan beberapa lainnya. Jika operasi menggunakan lebih dari dua relasi, maka itu dilakukan secara berurutan untuk dua yang pertama, dan kemudian untuk relasi terakhir dan yang ketiga, dll.



Dengan kata lain, operasi ini didefinisikan untuk dua relasi. Dalam operasi pada relasi, diasumsikan bahwa domain untuk menentukan relasi (operan dan hasil) adalah sama, aritas relasi tersebut bertepatan, dan hasil operasinya lagi-lagi merupakan relasi dengan aritas yang sama. Sebagai contoh, kita akan mempertimbangkan operasi pada relasi biner P dan Q yang didefinisikan pada himpunan diskrit

= {a1, a2, a3, a4} oleh matriks boolean (sebagai aturan, nol tidak cocok dengan matriks):





1. Persimpangan (P ∩ Q) adalah relasi yang dibentuk oleh semua pasangan elemen dari A yang termasuk dalam kedua relasi, yaitu umum untuk P dan Q,

P ∩ Q = {(ai aj) | ((ai aj) є P) & ((ai aj) є Q)}.



Matriks rasio P ∩ Q diperoleh sebagai perpotongan Boolean dari matriks P dan Q:





Dengan tidak adanya pasangan umum seperti itu, persimpangan hubungan dikatakan kosong, yaitu itu adalah hubungan nol. Perpotongan relasi R1 dan R2 (R1∩R2) adalah relasi yang ditentukan oleh perpotongan himpunan bagian terkait dari A × A.



2. Serikat (PUQ). Penyatuan relasi R1 dan R2 (R1UR2) adalah relasi yang didefinisikan oleh penyatuan himpunan bagian terkait dari A × A. Rasio yang dibentuk oleh semua pasangan yang membentuk rasio P atau rasio Q, mis. oleh pasangan milik setidaknya satu relasi (ikat conn - atau

gabungan ) PUQ = {(ai aj) | ((ai aj) є P) ∨ ((ai aj) є Q)}.



Jika dalam himpunan A × A tidak ada pasangan lain yang tidak termasuk dalam relasi PUQ, dan perpotongannya nol, maka relasi P dan Q dikatakan membentuk relasi lengkap A × A jika digabungkan, dan sistemnya adalah partisi dari relasi lengkap ini. Gabungan matriks hubungan dibentuk sebagai jumlah Boolean dari matriks hubungan:





3. Selisih (P \ Q) adalah perbandingan yang dibentuk oleh pasangan-pasangan dari P yang tidak termasuk dalam relasi Q

P \ Q = {(ai aj) | ((ai aj) є P) & ((ai aj) ∉Q)}.



Perbedaan relasi dalam representasi matriks adalah





4. Perkalian hubungan. Pasangan terurut yang membentuk hubungan mungkin mengandung atau tidak elemen yang sama. Di antara pasangan yang memiliki elemen identik dalam komposisinya, mari kita pilih pasangan berurutan seperti itu, yang kita sebut berdekatan (berdampingan) dan yang memiliki elemen pertama pada pasangan kedua, dan elemen kedua pada pasangan pertama adalah sama. Mari kita definisikan hasil kali dari pasangan yang berdekatan sebagai pasangan berurutan:

(ai ak) ∙ (ak aj) => (ai aj).



Dalam teori graf, ini berarti bahwa pasangan yang berdekatan membentuk rute dari titik (ai) ke titik (aj) dalam transit melalui titik (ak), yang terdiri dari 2 busur yang berdekatan. Hasil kali dari busur ini adalah busur ketiga dari titik (ai) ke titik (aj), yang mengimplementasikan transisi antara titik ekstrim dari rute ke arah yang sama, melewati titik tengah (ak). Busur (ai aj) dikatakan menutup titik-titik ini secara langsung.



5. Perbedaan simetris (P∆Q) - rasio yang dibentuk oleh pasangan-pasangan yang termasuk dalam PUQ gabungan, tetapi tidak termasuk dalam perpotongan P∩Q. Bentuk definisi lain menjelaskan nama operasi: P∆Q dibentuk oleh pasangan terurut yang merupakan gabungan dari perbedaan P \ Q dan Q \ P. Jadi, ekspresi selisih simetris dapat ditulis dengan dua cara yang berbeda:

P∆ Q = (PU Q) \ (P ∩ Q) = (P \ Q) U (Q \ P).



Matriks perbedaan simetris adalah:





Dari catatan terakhir dapat disimpulkan bahwa operasi perbedaan simetris memungkinkan permutasi operan, yaitu komutatif.



5. Komposisi atau hasil kali (P ∙ Q) - relasi yang dibentuk oleh semua pasangan yang:

P ∙ Q = {(ai aj) | ((ai ak) є P) & ((ak aj) є Q)}.



Dengan kata lain, setiap pasangan terurut dalam relasi yang dihasilkan merupakan hasil perkalian dari pasangan yang berdekatan, dimana pasangan pertama termasuk dalam hubungan faktor pertama, kedua - dengan hubungan faktor kedua. Operasi komposisi tidak komutatif.



Komposisi (◦Q) pada himpunan M adalah relasi R yang didefinisikan pada himpunan yang sama M yang berisi pasangan (x, y) jika terdapat Z є M sehingga (x, z) є P dan (z, y) є Q.



Dalam representasi matriks relasi, matriks komposisi relasi sama dengan hasil perkalian Boolean dari matriks relasi asli:





Kasus khusus dari komposisi hubungan adalah kuadrat hubungan.



Dapat ditunjukkan dengan menggunakan induksi bahwa derajat ke-n dari suatu relasi didefinisikan secara rekursif dengan rumus: P ⁿ = P ^n-1 ◦, ini berarti bahwa pasangan (x, y) є P ⁿ dalam kasus ketika dalam matriks terdapat rantai elemen: sedemikian rupa sehingga (xi, xi + 1) є P, 1 <i <n - 1.



Operasi komposisi memiliki sifat asosiatif (seperti hasil kali matriks).



Komposisi relasi pada himpunan M adalah hasil komposisi relasi berpasangan untuk setiap susunan tanda kurung. Area untuk pengaturan hasil komposisi tidak berubah.



Komposisi matriks relasi Boolean dibentuk sebagai hasil perkalian Boolean matriks relasi ini.



Tabel 3. Katalog hubungan biner (n = 3). Dapat diklik