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

Автор: Aport Вторник, Январь 27th, 2015 Нет комментариев

Рубрика: Разное

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

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

Поехали. Статья базируется на предыдущей статье, но с использованием хранения вершин (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’

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

 

Источник: yapro.ru

Оставить комментарий

Чтобы оставлять комментарии Вы должны быть авторизованы.

Похожие посты