Jalur dan lompatan panjang variabel

Pola MATCH dengan satu relasi hanya menjawab pertanyaan tentang tetangga langsung, sedangkan banyak pertanyaan graf menyangkut rantai hubungan yang panjangnya tidak diketahui sebelumnya. Topik ini membahas jalur (path) sebagai hasil pola MATCH serta lompatan panjang variabel (variable-length relationship), yaitu pola seperti -[:KENAL*2..3]- yang boleh melintasi dua hingga tiga relasi berturut-turut. Setelah topik ini dibaca, penulisan pola berulang beserta batas bawah dan atasnya, penelusuran dua arah, dan estimasi biaya penelusuran tanpa batas dapat dipraktikkan pada dataset jaringan sosial yang menyertai modul ini.

Dataset jaringan sosial#

Seluruh contoh pada modul ini menggunakan satu dataset kecil yang sama, yaitu jaringan sosial berisi tujuh node berlabel :Person dengan properti name dan kota, ditambah dua node :Hobi. Relasi :KENAL menghubungkan orang-orang tersebut dalam satu rantai utama Eko, Fajar, Gita, Hana, ditambah cabang Eko, Iwan, Hana, serta dua cabang pendek menuju Jihan dan Rara. Arah relasi diperlakukan bermakna, misalnya (Eko)-[:KENAL]->(Fajar) berarti Eko mengenal Fajar. Selain itu, hanya Hana dan Fajar yang dihubungkan ke hobi melalui relasi :PUNYA_HOBI, sehingga ketiadaan data nantinya memunculkan nilai null secara alami.

Skrip setup.cypher berikut membangun seluruh dataset dengan MERGE, sehingga skrip ini idempoten dan aman dijalankan berulang tanpa menduplikasi data.

// Dataset modul Pola kueri: jaringan sosial dengan relasi KENAL dan hobi.
// Skrip ini idempoten, sehingga aman dijalankan lebih dari satu kali.

// Tujuh orang beserta kota asalnya
MERGE (p:Person {name: 'Eko'}) SET p.kota = 'Bandung';
MERGE (p:Person {name: 'Fajar'}) SET p.kota = 'Bandung';
MERGE (p:Person {name: 'Gita'}) SET p.kota = 'Semarang';
MERGE (p:Person {name: 'Hana'}) SET p.kota = 'Surabaya';
MERGE (p:Person {name: 'Iwan'}) SET p.kota = 'Semarang';
MERGE (p:Person {name: 'Jihan'}) SET p.kota = 'Bandung';
MERGE (p:Person {name: 'Rara'}) SET p.kota = 'Yogyakarta';

// Dua hobi
MERGE (h:Hobi {name: 'Fotografi'});
MERGE (h:Hobi {name: 'Bersepeda'});

// Rantai KENAL, kedua ujung diikat variabel agar MERGE hanya menangani relasinya
MATCH (a:Person {name: 'Eko'}), (b:Person {name: 'Fajar'}) MERGE (a)-[:KENAL]->(b);
MATCH (a:Person {name: 'Fajar'}), (b:Person {name: 'Gita'}) MERGE (a)-[:KENAL]->(b);
MATCH (a:Person {name: 'Gita'}), (b:Person {name: 'Hana'}) MERGE (a)-[:KENAL]->(b);
MATCH (a:Person {name: 'Eko'}), (b:Person {name: 'Iwan'}) MERGE (a)-[:KENAL]->(b);
MATCH (a:Person {name: 'Iwan'}), (b:Person {name: 'Hana'}) MERGE (a)-[:KENAL]->(b);
MATCH (a:Person {name: 'Gita'}), (b:Person {name: 'Jihan'}) MERGE (a)-[:KENAL]->(b);
MATCH (a:Person {name: 'Fajar'}), (b:Person {name: 'Rara'}) MERGE (a)-[:KENAL]->(b);

// Hobi hanya dimiliki sebagian orang, sehingga null muncul secara alami
MATCH (a:Person {name: 'Hana'}), (b:Hobi {name: 'Fotografi'}) MERGE (a)-[:PUNYA_HOBI]->(b);
MATCH (a:Person {name: 'Fajar'}), (b:Hobi {name: 'Bersepeda'}) MERGE (a)-[:PUNYA_HOBI]->(b);

Cara termudah memuat skrip tersebut adalah mengalirkannya ke cypher-shell melalui pipa, atau mengeksekusinya dari Neo4j Browser. Perhatikan bahwa setiap relasi dibuat dalam pernyataan tersendiri yang mengikat kedua ujungnya dengan MATCH lebih dahulu. Pola ini penting karena MERGE pada pola yang ujungnya belum terikat akan membuat node baru, bukan menggunakan node yang sudah ada.

# tidak-dijalankan
# memuat dataset melalui cypher-shell, kata sandi diminta interaktif
cypher-shell -a bolt://localhost:7687 -u neo4j -f setup.cypher

Susunan dataset digambarkan oleh diagram berikut. Rantai panjang Eko menuju Hana inilah yang menjadi bahan latihan lompatan panjang variabel.

Jalur sebagai hasil pola MATCH#

Dengan mengikat pola ke sebuah variabel jalur, misalnya p, hasil pencocokan tidak lagi berupa pasangan node yang terpisah, melainkan seluruh lintasan beserta node dan relasi di dalamnya. Fungsi length() menerima sebuah jalur dan mengembalikan panjangnya, yaitu jumlah relasi yang dilalui. Kueri berikut menunjukkan satu relasi KENAL biasa yang diikat ke variabel p, sehingga keluarannya memuat panjang satu.

MATCH p = (a:Person {name: 'Eko'})-[:KENAL]->(b:Person {name: 'Fajar'})
RETURN a.name AS dari, b.name AS ke, length(p) AS panjang;

dari, ke, panjang
"Eko", "Fajar", 1

Variabel p tetap dapat diabaikan apabila yang dibutuhkan hanya ujung-ujungnya, tetapi keberadaannya membuka akses ke isi jalur. Selain length(), sebuah jalur juga dapat diurai menjadi daftar node dan daftar relasinya melalui fungsi nodes() dan relationships(), dan penguraian semacam itu dibahas pada topik tentang pengolahan list. Nilai length(p) juga dapat ditempatkan pada WHERE untuk menyaring jalur menurut panjangnya dan pada ORDER BY untuk mengurutkan baris hasil. Untuk saat ini, panjang jalur sudah cukup sebagai ukuran yang akan disaring dan dibatasi pada bagian-bagian berikutnya.

Lompatan panjang variabel#

Simbol bintang (*) pada tipe relasi mengubah pola menjadi pola berulang, yaitu relasi KENAL boleh muncul berkali-kali secara berturut-turut dalam satu jalur. Notasi ini disebut lompatan panjang variabel karena banyaknya relasi tidak ditulis tetap, melainkan ditentukan oleh rentang tertentu. Batas panjang ditulis tepat setelah bintang, dan kueri berikut meminta jalur dari Eko yang melintasi dua sampai tiga relasi KENAL secara berarah.

MATCH p = (a:Person {name: 'Eko'})-[:KENAL*2..3]->(b:Person)
RETURN a.name AS dari, b.name AS ke, length(p) AS panjang
ORDER BY panjang, ke;

dari, ke, panjang
"Eko", "Gita", 2
"Eko", "Hana", 2
"Eko", "Rara", 2
"Eko", "Hana", 3
"Eko", "Jihan", 3

Hasilnya memuat lima jalur, dan nama tujuan yang sama boleh muncul lebih dari sekali karena ada lebih dari satu jalur menuju tujuan tersebut. Hana terjangkau lewat Iwan dalam dua lompatan dan lewat Fajar lalu Gita dalam tiga lompatan, sesuai rantai pada diagram dataset. Beberapa notasi batas yang lazim dirangkum pada tabel berikut.

Batas bawah dan atas keduanya opsional, tetapi menetapkan keduanya dianjurkan pada graf berukuran nyata. Kueri berikut memperketat pola sebelumnya menjadi tepat dua lompatan, dan hasilnya hanya tiga tujuan. Ketiga tujuan sama dengan baris dua lompatan pada keluaran sebelumnya, sedangkan seluruh baris tiga lompatan tidak lagi muncul.

MATCH (a:Person {name: 'Eko'})-[:KENAL*2]->(b:Person)
RETURN b.name AS tujuan
ORDER BY b.name;

tujuan
"Gita"
"Hana"
"Rara"

Penelusuran dua arah#

Apabila panah pada pola dihilangkan, relasi dicocokkan ke kedua arah, sehingga penelusuran tidak lagi mengikuti makna “mengenal” secara satu arah. Pola dua arah sangat berguna untuk menjawab pertanyaan jangkauan, misalnya siapa saja yang terhubung dengan Jihan melalui rantai KENAL apa pun arahnya. Kueri berikut membatasi panjangnya maksimal empat lompatan dengan batas ..4 dan menggunakan DISTINCT karena satu orang yang sama dapat terjangkau melalui beberapa jalur berbeda.

MATCH (a:Person {name: 'Jihan'})-[:KENAL*..4]-(b:Person)
RETURN DISTINCT b.name AS terjangkau
ORDER BY terjangkau;

terjangkau
"Eko"
"Fajar"
"Gita"
"Hana"
"Iwan"
"Rara"

Seluruh enam orang lainnya terjangkau dari Jihan, karena graf pada dataset ini terhubung menjadi satu komponen. Jihan sendiri tidak muncul karena satu jalur tidak boleh melalui relasi yang sama dua kali, sehingga penelusuran tidak dapat kembali ke titik awalnya. Perlu dicatat bahwa penelusuran dua arah memperbanyak jumlah jalur kandidat dibandingkan penelusuran berarah, sehingga biayanya lebih mahal pada graf yang sama. Dokumentasi Cypher terbaru juga menyediakan bentuk alternatif bernama pola terkuantifikasi (quantified path pattern) untuk kebutuhan yang sama, sedangkan notasi *min..max yang lebih tua tetap didukung penuh dan menjadi bentuk yang digunakan di sepanjang modul ini.

Biaya penelusuran tanpa batas#

Setiap tambahan satu lompatan pada pola tanpa batas atas memperbanyak jumlah jalur kandidat secara cepat karena setiap cabang yang ditemukan dilalui lagi dari ujungnya. Pada dataset kecil ini efeknya masih mudah diukur dengan count(). Kueri pertama menghitung jalur dua arah dari Eko dengan batas atas dua, lalu kueri kedua memperlonggar batasnya menjadi empat.

MATCH (a:Person {name: 'Eko'})-[:KENAL*..2]-(b:Person)
RETURN count(*) AS jalur;

jalur
5

MATCH (a:Person {name: 'Eko'})-[:KENAL*..4]-(b:Person)
RETURN count(*) AS jalur;

jalur
11

Melonggarkan batas dari dua menjadi empat lebih dari sekali menggandakan jumlah jalur pada graf yang hanya berisi tujuh node. Tanpa batas atas, jumlah jalurnya bertambah lagi menjadi empat belas, dan kueri berikut masih aman dijalankan hanya karena datanya kecil.

MATCH (a:Person {name: 'Eko'})-[:KENAL*]-(b:Person)
RETURN count(*) AS jalur;

jalur
14

Dokumentasi resmi menyarankan tiga cara meredam ledakan jalur, yaitu menetapkan batas atas, memperketat pola dengan label node atau arah relasi, dan menambahkan predikat di dalam pola. Untuk pertanyaan analitik yang memang memerlukan penelusuran luas, seperti jalur berbobot atau keterhubungan seluruh pasangan node, pustaka GDS menyediakan algoritma yang dikerjakan pada proyeksi graf dalam memori dan dibahas tersendiri pada modul algoritma graf di jalur ini.

Kesalahan umum#

Kesalahan pertama adalah tidak menyadari bahwa satu tujuan dapat dicapai lewat beberapa jalur. Kueri panjang variabel mengembalikan satu baris untuk setiap jalur, bukan satu baris untuk setiap tujuan, sehingga hasil seperti Hana yang muncul dua kali pada bagian sebelumnya bukanlah cacat data. Perbaikannya adalah menambahkan DISTINCT pada kolom tujuan atau mengagregasi hasilnya apabila jumlah jalur justru menjadi informasi yang dicari.

Kesalahan kedua adalah menganggap pola berulang boleh melintasi relasi yang sama dua kali. Secara default Cypher hanya menelusuri relasi yang belum pernah digunakan dalam satu jalur, sehingga siklus pendek seperti bolak-balik pada relasi yang sama tidak muncul sebagai hasil. Apabila penelusuran dengan relasi berulang memang dikehendaki, pola perlu ditandai secara eksplisit dengan mode elemen yang dapat diulang, dan kebutuhan semacam itu jarang muncul pada pemodelan jaringan sosial.

Kesalahan ketiga adalah menyalin pola tanpa batas atas dari graf kecil ke graf produksi. Kueri yang menjawab dalam hitungan milidetik pada data uji dapat berjalan berjam-jam setelah data nyata dimuat, karena pertumbuhannya eksponensial. Praktik yang dianjurkan adalah menetapkan batas atas sejak kueri pertama ditulis, lalu melonggarnya hanya apabila hasilnya terbukti belum memadai.

Ringkasan#

• Variabel jalur dari pola MATCH p = (...) menyimpan lintasan utuh, dan length(p) mengembalikan jumlah relasinya.
• Notasi *min..max pada tipe relasi mengulang relasi dalam rentang panjang tertentu, dengan batas bawah default satu apabila tidak ditulis.
• Penghapusan panah membuat pola dicocokkan ke kedua arah sehingga jangkauan terukur tanpa memedulikan arah relasi.
• Pola tanpa batas atas berisiko tumbuh eksponensial, sehingga batas atas, arah, atau pustaka GDS diperlukan pada graf nyata.

Referensi#

• Variable-length paths — Neo4j Docs — Penjelasan pola panjang variabel beserta peringatan pertumbuhan eksponensial dan cara meredamnya.
• MATCH — Neo4j Docs — Referensi klausa MATCH, termasuk pengikatan jalur dan pencocokan pola berulang.