OrientDB - работа с деревьями

В этой статье я попробую рассказать о том, как работать с пересечениями, для того, чтобы делать выборку деревьев.

И для начала, кому интересно:

Поехали. Статья базируется на предыдущей статье, но с использованием хранения вершин (Vertex) в отдельном наследуемом классе My. И поэтому, я все же напомню, мы должны выполнить команды:

create class My extends V

create vertex My set city="Rome"
create vertex My set city="London"
create vertex My set city="Berlin"
create vertex My set city="Madrid"
create vertex My set city="Paris"

create edge from #12:0 to #12:4 set distance=1106
create edge from #12:4 to #12:0 set distance=1106
create edge from #12:4 to #12:3 set distance=1054
create edge from #12:3 to #12:4 set distance=1054
create edge from #12:3 to #12:1 set distance=1267
create edge from #12:1 to #12:3 set distance=1267
create edge from #12:1 to #12:2 set distance=930
create edge from #12:2 to #12:1 set distance=930
create edge from #12:2 to #12:0 set distance=1183
create edge from #12:0 to #12:2 set distance=1183

Итак, предлагаю все исследования проводить на пером попавшемся объекте, а именно #12:0:

orientdb {cities}> select from #12:0

----+-----+--------+--------+----
#   |@RID |out_    |in_     |city

----+-----+--------+--------+----
0   |#12:0|[size=2]|[size=2]|Rome

----+-----+--------+--------+----

Для начала предлагаю обратится к документации, и попробовать задействовать пару функций:

Функция in() - получает прилегающие входящие вершины, начиная с текущей записи как Vertex.

orientdb {cities}> select in() from #12:0        

----+-----+----
#   |@RID |in  

----+-----+----
0   |#-2:1|[2] 

----+-----+----

но погодите, ничего не понятно ведь, давайте для понимания воспользуемся функцией expand(<field>) - которая расширяет коллекции в поле <Field> и использует его как результат:

orientdb {cities}> select expand(in()) from #12:0

----+-----+--------+--------+------
#   |@RID |in_     |out_    |city  

----+-----+--------+--------+------
0   |#12:4|[size=2]|[size=2]|Paris 
1   |#12:2|[size=2]|[size=2]|Berlin

----+-----+--------+--------+------

фуф, теперь все понятно, Rome связан с Paris и Berlin.

Обратите внимание, используя функцию in() в примере выше, мы нашли объекты, к которым привязан объект #12:0, и это вовсе не объекты, которые привязаны к #12:0, видите разницу? А вот чтобы найти объекты, которые привязаны к объекту #12:0 нам нужна функция out() - она получает прилегающие исходяще вершины, начиная с текущей записи как Vertex:

orientdb {cities}> select expand(out()) from #12:0

----+-----+--------+--------+------
#   |@RID |in_     |out_    |city  

----+-----+--------+--------+------
0   |#12:4|[size=2]|[size=2]|Paris 
1   |#12:2|[size=2]|[size=2]|Berlin
----+-----+--------+--------+------

ага, видим, что Rome связан с Paris и  Berlin. И очень важный момент по размеру связей в стобцах, напомню:

in_ - сколько вершин у этого объекта (сколько родителей)

out_ - скольким объектам этот объект является вершиной (сколько дочерних объектов)

Понятно? Тогда поехали дальше.

Попробуем разобраться с пересечениями (travers). И сразу нюанс: непонятно почему, но указав пересечению неизвестное поле erunda мы получаем аналог обычного селекта:

orientdb {cities}> traverse erunda from #12:0

----+-----+--------+--------+----
#   |@RID |out_    |in_     |city

----+-----+--------+--------+----
0   |#12:0|[size=2]|[size=2]|Rome

----+-----+--------+--------+----

Давайте попробуем просмотреть пересечения поля out_:

orientdb {cities}> traverse out_ from #12:0

----+------+--------+--------+----+--------+-----+-----
#   |@RID  |out_    |in_     |city|distance|out  |in   

----+------+--------+--------+----+--------+-----+-----
0   |#12:0 |[size=2]|[size=2]|Rome|null    |null |null 
1   |#10:1 |null    |null    |null|1106    |#12:0|#12:4
2   |#10:10|null    |null    |null|1183    |#12:0|#12:2

----+------+--------+--------+----+--------+-----+-----

как видите, мы получили нашу строчку (словно мы сделали селект) + две строки из класса E. Если не верите мне, что это именно класс E, то следующий запрос Вас убедит:

orientdb {cities}> select @rid, @class from (traverse out_ from #12:0)

----+-----+------+-----
#   |@RID |rid   |class

----+-----+------+-----
0   |#-2:1|#12:0 |My   
1   |#-2:2|#10:1 |E    
2   |#-2:3|#10:10|E    

----+-----+------+-----

что нам это дало? да просто мы одним запросом вытащили объект #12:0 из класса My и все его ребра (в нашем случае два ребра) из класса E.

Давайте добавим еще одно ребро, которое нам поможет разобраться в одной из ситуаций ниже:

create edge from #12:0 to #12:3 set distance=1234

Напомню, нас интересует дерево, но сначала попробуем попрактиковаться с функциями out() и in() используя traverse.

orientdb {cities}> traverse out() from #12:0

----+-----+--------+--------+------
#   |@RID |out_    |in_     |city  

----+-----+--------+--------+------
0   |#12:0|[size=3]|[size=2]|Rome  
1   |#12:4|[size=2]|[size=2]|Paris 
2   |#12:3|[size=2]|[size=2]|Madrid
3   |#12:1|[size=2]|[size=2]|London
4   |#12:2|[size=2]|[size=2]|Berlin

----+-----+--------+--------+------

Ёшкин кот, использование in() и out() дают одинаковый результат! И правильно, ведь с помощью их мы нашли пересечение всего со всем и в результате видим кол-во пересечений. 

Не удивляйтесь, но применять эти функций нам не нужно, и познакомились мы с ними именно для того, чтобы понять это.

Все что нам понадобится, это простая звездочка, пример из документации:

orientdb {cities}> traverse * from #12:0

----+------+--------+--------+------+--------+-----+-----
#   |@RID  |out_    |in_     |city  |distance|out  |in   

----+------+--------+--------+------+--------+-----+-----
0   |#12:0 |[size=3]|[size=2]|Rome  |null    |null |null 
1   |#10:1 |null    |null    |null  |1106    |#12:0|#12:4
2   |#12:4 |[size=2]|[size=2]|Paris |null    |null |null 
3   |#10:4 |null    |null    |null  |1054    |#12:3|#12:4
4   |#12:3 |[size=2]|[size=3]|Madrid|null    |null |null 
5   |#10:3 |null    |null    |null  |1054    |#12:4|#12:3
6   |#10:6 |null    |null    |null  |1267    |#12:1|#12:3
7   |#12:1 |[size=2]|[size=2]|London|null    |null |null 
8   |#10:5 |null    |null    |null  |1267    |#12:3|#12:1
9   |#10:8 |null    |null    |null  |930     |#12:2|#12:1
10  |#12:2 |[size=2]|[size=2]|Berlin|null    |null |null 
11  |#10:7 |null    |null    |null  |930     |#12:1|#12:2
12  |#10:10|null    |null    |null  |1183    |#12:0|#12:2
13  |#10:9 |null    |null    |null  |1183    |#12:2|#12:0
14  |#10:0 |null    |null    |null  |1234    |#12:0|#12:3
15  |#10:2 |null    |null    |null  |1106    |#12:4|#12:0

----+------+--------+--------+------+--------+-----+-----

таким образом, мы находим все out_ нашего объекта #12:0, т.е. это и есть наше дерево.

Но останавливаться мы не станем, а немного усложним задачу. И для начала посмотрим глубины ветвления нашего дерева с помощью магической переменной $depth (которая показывает нам глубину связей):

orientdb {cities}> select @rid, @class, city, $depth, out, in from (traverse * from #12:0)

----+------+------+-----+------+------+-----+-----
#   |@RID  |rid   |class|city  |$depth|out  |in   

----+------+------+-----+------+------+-----+-----
0   |#-2:1 |#12:0 |My   |Rome  |0     |null |null 
1   |#-2:2 |#10:1 |E    |null  |1     |#12:0|#12:4
2   |#-2:3 |#12:4 |My   |Paris |2     |null |null 
3   |#-2:4 |#10:4 |E    |null  |3     |#12:3|#12:4
4   |#-2:5 |#12:3 |My   |Madrid|4     |null |null 
5   |#-2:6 |#10:3 |E    |null  |5     |#12:4|#12:3
6   |#-2:7 |#10:6 |E    |null  |5     |#12:1|#12:3
7   |#-2:8 |#12:1 |My   |London|6     |null |null 
8   |#-2:9 |#10:5 |E    |null  |7     |#12:3|#12:1
9   |#-2:10|#10:8 |E    |null  |7     |#12:2|#12:1
10  |#-2:11|#12:2 |My   |Berlin|8     |null |null 
11  |#-2:12|#10:7 |E    |null  |9     |#12:1|#12:2
12  |#-2:13|#10:10|E    |null  |9     |#12:0|#12:2
13  |#-2:14|#10:9 |E    |null  |9     |#12:2|#12:0
14  |#-2:15|#10:0 |E    |null  |5     |#12:0|#12:3
15  |#-2:16|#10:2 |E    |null  |3     |#12:4|#12:0

----+------+------+-----+------+------+-----+-----

советую остановиться здесь и внимательно посмотреть, как OrientDB считает глубину.

Для простоты виденья сделаем такой запрос:

orientdb {cities}> select @rid, @class, city, $depth from (traverse * from #12:0) where @class = 'My'

----+-----+-----+-----+------+------
#   |@RID |rid  |class|city  |$depth

----+-----+-----+-----+------+------
0   |#-2:1|#12:0|My   |Rome  |0     
1   |#-2:2|#12:4|My   |Paris |2     
2   |#-2:3|#12:3|My   |Madrid|4     
3   |#-2:4|#12:1|My   |London|6     
4   |#-2:5|#12:2|My   |Berlin|8     

----+-----+-----+-----+------+------

Итак, благодаря магической переменной $depth мы можем делать выборку указывая глубину дерева:

orientdb {cities}> select @rid, @class, city, $depth from (traverse * from #12:0) where @class = 'My' AND $depth < 7

----+-----+-----+-----+------+------
#   |@RID |rid  |class|city  |$depth

----+-----+-----+-----+------+------
0   |#-2:1|#12:0|My   |Rome  |0     
1   |#-2:2|#12:4|My   |Paris |2     
2   |#-2:3|#12:3|My   |Madrid|4     
3   |#-2:4|#12:1|My   |London|6     

----+-----+-----+-----+------+------

вот так, мы получили желаемый результат.

Не смотря на то, что запрос у нас получился правильным, Артём Оробец советует перенести $depth < 7 в траверс, чтобы ограничить перебор вершин во внутреннем запросе, т.е. правильней будет так:

select @rid, @class, city, $depth from (traverse * from #12:0 where $depth < 7) where @class = 'My'

Надеюсь статья получилась доходчивая, но если будут вопросы, вэлком в комменты, и удачки в изучении.

Оцени публикацию:
  • 5,21
Оценили человек: 5
Теги : OrientDB

Похожие статьи:

Справочники и учебники:


Комментарии посетителей:
  •    Да все хорошо написано в рамках того, что описано в документации. Но  как быть с поиском маршрута от одного узла  к другому. Мне кажется именно такие задачи должны решаться с помощью графов.
     Пытался решить задачу Neo4j, но в силу убогости REST API  отказался от нее. Сейчас патыюсь понять как это сделать в orientDB. И опять какие  то простые примеры на уровне insert update   и  select * from .
    Как искать цепочки. И вообще это возможно ? Или все загонять в массив и писать свой алгоритм перебора ? Опять в  каменный век?
    30 июля 2014, 08:30 коммент полезен : 0 # Juno24
    • Все просто, когда Вы делаете запрос связанных объектов, то вытягивается не строка, а дерево, т.е. многомерный массив. По Вашему комментарию кажется, что Вы либо не связывали объекты (строки), либо не вытягивали связанные объекты (строки). В этом нет ничего страшного, потому что я так же, как понял смысл связей, когда в пхп распечатал полученный результат. Попробуйте сделать это с помощью например функции print_r
      01 августа 2014, 08:35 коммент полезен : 0 # Yapro (гость)
Предложения и пожелания:
Ваше имя:
Ваш E-mail:
Сколько будет Οдин + Τри
Главная
X

Новые заметки:

Про что мы забываем когда делаем оценку задачи по времени

Список вопросов для собеседования разработчика по телефону

Symfony2 авторизация без Doctrine2 для чайника

Phpstorm7 LiveEdit

Жесткий хабр или не хабр, тогда кто?

Яндекс.Деньги мошенничество

Как узнать какие страницы в поиске яндекса или это секрет

Последние комменты:

Yapro CMS:

Здравствуйте, Гость | Войти | Регистрация | Карта сайта | RSS ленты | Ошибка в тексте? Выделите её мышкой и нажмите: Ctrl + Enter

youtube.com/watch?v=7hFivbgIEqk

При полном или частичном использовании материалов данного сайта, ссылка на сайт "yapro.ru" обязательна как на источник информации.
Автоматический импорт материалов и информации с сайта запрещен.
Copyrights © 2007 - 2018 YaPro.Ru

Главная » Веб-мастеру » MySQL »