Path — grafdagi tugunlar va ularni ketma-ket bog‘laydigan qirralardan tashkil topgan yo‘l hisoblanadi. Grafik ma’lumotlar bazasida path ikki obyekt qanday aloqalar zanjiri orqali bog‘langanini ifodalaydi. Masalan, foydalanuvchidan tashkilotgacha bo‘lgan “a’zo”, “guruhga tegishli” va “tashkilot tarkibida” qirralari bitta yo‘lni hosil qilishi mumkin.
Matematik mazmun
Graf nazariyasida yurish qirralar bo‘ylab istalgan ketma-ketlik bo‘lib, tugun yoki qirra takrorlanishi mumkin. Trail qirrani takrorlamaydi, oddiy path esa tugunni takrorlamaydi. Sikl boshlang‘ich va oxirgi tuguni bir xil bo‘lgan yopiq yo‘ldir. Amaliy mahsulotlar “path” atamasiga turlicha aniq cheklov berishi mumkin, shuning uchun so‘rov tilining semantikasini tekshirish zarur.
Yo‘l uzunligi odatda qirralar soni bilan o‘lchanadi. Vaznli grafda esa qirralarning narx, masofa yoki vaqt qiymatlari yig‘iladi. Eng kam qirrali yo‘l vaznli eng arzon yo‘l bilan har doim bir xil emas.
Grafik so‘rovlar
Grafik so‘rov tilida yo‘l naqsh orqali tavsiflanadi. Quyidagi Cypher misoli foydalanuvchi bilan sahifa orasida bir–uch qadamli KUZATADI zanjirini izlaydi:
MATCH p=(a:Foydalanuvchi)-[:KUZATADI*1..3]->(b:Sahifa)
WHERE a.id = $id
RETURN p
O‘zgaruvchan uzunlik qulay, biroq yuqori tarmoqlanishda kombinatsiyalar soni tez o‘sadi. Cheklanmagan uzunlikdagi so‘rov katta grafda juda qimmat yoki tugamaydigan izlanishga o‘xshab qolishi mumkin. Boshlang‘ich tugunni indeks orqali toraytirish, maksimal chuqurlik belgilash, qirra turi va xususiyatlarini filtrlash muhim.
Algoritmlar
Vaznsiz grafdagi eng qisqa yo‘l ko‘pincha kenglik bo‘yicha qidiruv bilan topiladi. Manfiy bo‘lmagan vaznlar uchun Dijkstra algoritmi keng qo‘llanadi. Evristik ma’lumot mavjud bo‘lsa, A* maqsadga yo‘nalgan qidiruvni qisqartirishi mumkin. Manfiy vaznlar yoki barcha juftliklar uchun boshqa algoritmlar talab etiladi.
“Eng qisqa” mezoni biznes ma’nosiga mos bo‘lishi lozim. Yetkazib berishda kilometr, vaqt va to‘lov turli natijalarni beradi. Xavfsizlik tahlilida esa eng kam imtiyoz o‘tishlari bilan maqsadga yetish yo‘li qiziq bo‘lishi mumkin. Bir nechta teng yo‘l mavjud bo‘lsa, tizim bittasini yoki barchasini qaytarishi ham alohida belgilanadi.
Natijani talqin qilish
Path faqat tugunlar ro‘yxati emas: qirralarning turi, yo‘nalishi va xususiyatlari ham mazmunning bir qismidir. Vaqtga bog‘liq grafda ketma-ket aloqalar sanasi mantiqan oshib borishi kerak bo‘lishi mumkin; aks holda topilgan yo‘l topologik jihatdan to‘g‘ri, tarixiy jihatdan imkonsiz chiqadi.
Katta yo‘llarni mijoz dasturiga to‘liq uzatish xotira va tarmoq sarfini oshiradi. Ko‘pincha faqat uzunlik, umumiy vazn, muhim tugunlar yoki dastlabki bir nechta natija olinadi. Ruxsat tizimida yo‘l mavjudligi qarorni asoslashga yordam beradi, ammo noto‘g‘ri yoki eskirgan qirra ruxsat xulosasini buzishi mumkin. Shu sababli grafdagi aloqa manbasi va yangilanish vaqti ham nazorat qilinadi.
Xavfsizlik va chegaralar
Foydalanuvchi boshqaradigan chuqurlikni tekshirmasdan so‘rovga qo‘shish xizmatni resurs jihatdan band qilishi mumkin. Maksimal qadam, natija soni va bajarish muddati server tomonidan cheklanadi. Ruxsat grafigida esa yo‘lni topishning o‘zi yetarli emas: har bir qirra joriy va ishonchli manbadan kelgani, inkor qoidalari ustunligi ham tekshiriladi. Natija keshi ishlatilsa, graf yangilanganda eskirgan yo‘llarni bekor qilish mexanizmi talab etiladi. Chegaralar audit jurnalida qayd etilib, g‘ayrioddiy qidiruvlar kuzatiladi.
Bog‘liq tushunchalar
Graf, Traversiya, Eng qisqa yo‘l, Dijkstra algoritmi, Sikl, Pattern matching