Элементарный алгоритм - волновой
Примеры
Пример 1.
Выбрать сотрудников, зарплата которых выше средней в их подразделении,
в порядке убывания зарплаты.
create table department {
id num primary key,
name string,
sum num fictional,
amount num fictional
};
create table employee {
id num primary key,
name string,
salary num,
department num references department (id)
};
Запрос таков:
department.employee[^.sum
^.sum+salary ^.amount^.amount+1];
department[#sum #amount].employee[-1§salary>^.sum/^.amount] 
;
Вывод базы данных приведен ниже
(поле "department" таблицы "employee" не выводится,
т.к. оно уже использовано при построении выходных данных).
<department id="1" name="Technical">
<employee id="54" name="Fraud" salary="3200">
<employee id="72" name="Kitter" salary="3100">
<employee id="31" name="Tomson" salary="3000">
</department>
<department id="2" name="Marketting">
<employee id="25" name="Johnson" salary="4100">
<employee id="64" name="Smith" salary="4000">
</department>
Пример 2.
Пусть существует ряд городов,
которые сообщаются рейсами некоторого транспорта без промежуточных остановок.
Требуется узнать:
- по каким дням недели есть прямые рейсы из города "a" в город "b"
- как в понедельник можно добраться из города "a" в город "b"
- нужно вылететь из города "a" в понедельник и вернуться в него обратно в пятницу,
посетив города "b", "c", "d".
В какой последовательности следует посещать города,
чтобы не совершать более одного перелета в день
Все названия городов хранятся в таблице "city".
Следующим звеном ("flight") в дереве является список городов,
в которые можно вылететь из данного
(условиями такой возможности являются наличие рейса и достаточное время для пересадки),
поля
"c1" - город отправления, "c2" - город прибытия,
"t1" - время отправления, "t2" - время прибытия,
"day" - дни недели, по которым осуществляется перелет.
Адрес города "a" находится в поле "tab.from", адрес города "b" - в поле "tab.to",
адреса городов "b", "c", "d" - в таблице "through".
create table city (
id num primary key,
name string
);
create table flight (
c1 num references city (id),
c2 num references city (id),
t1 time,
t2 time,
day weekdays
);
create table through (
ref num references city (id)
);
create table tab (
from num,
to num
);
Ответ на первый вопрос:
tab.from -> #city.flight/c1:c2[#c1 #c2].#city[id=tab.to] ;
<flight t1="5.30" t2="8.30" day="sunday">
<flight t1="7.30" t2="10.30" day="monday">
<flight t1="9.30" t2="12.30" day="tuesday">
<flight t1="15.30" t2="18.30" day="wednesday">
<flight t1="17.30" t2="20.30" day="thursday">
<flight t1="19.30" t2="22.30" day="friday">
<flight t1="7.30" t2="10.30" day="saturday">
Ответ на второй вопрос:
tab.from -> #city.(flight/c1:c2[#day="monday" t1-^^.t2>30min].city)*||id=tab.to ;
<flight t1="5.30" t2="5.50">
<city id="15" name="C">
<flight t1="7.00" t2="11.00">
<city id="18" name="B">
</flight>
</city>
</flight>
<flight t1="5.10" t2="12.10">
...
<city id="18" name="B">
...
</flight>
А ответ на третий вопрос выглядит так.
tab.from -> city.flight/c1:c2[day="monday"].city[id<~through.ref].(
flight/c1:c2.city[id<~through.ref]
)*||day="friday" id=tab.from ;
<city id="18" name="A">
<flight t1="5.30" t2="13.00" day="monday">
<city id="23" name="D">
...
</city>
</flight>
<flight t1="5.30" t2="5.50" day="monday">
<city id="18" name="B">
<flight t1="7.00" t2="11.00" day="tuesday">
<city id="14" name="C">
<flight t1="12.00" t2="13.00" day="wednesday">
<city id="23" name="D">
<flight t1="14.00" t2="17.00" day="thursday">
<city id="15" name="A">
</flight>
</city>
</flight>
</city>
</flight>
</city>
</flight>
</city>
Пример 3.1
Пусть мы ищем в графе путь, проходящий через минимальное количество вершин.
Каждая вершина есть запись в таблице "point".
Связи между вершинами хранятся в таблице "bond".
Путь ищется из вершины, первичный ключ которой задан в поле "tab.from" (начальная вершина),
к вершине, первичный ключ которой задан в поле "tab.to" (конечная вершина),
таблица "tab" имеет единственную запись.
create table point (
id num primary key,
prev num references point (id) fictional
);
create table bond (
p1 num references point (id),
p2 num references point (id)
);
create table tab (
from num references point (id),
to num references point (id)
);
Переберем все вершины от начальной к конечной - распространяется волна перебора.
Каждая вершина в поле "prev" содержит первичный ключ вершины, из которой пришла волна.
Начальное значение установим равным "null" для всех вершин.
point[prevnull];
|
-- update point set prev=null;
|
Каждую из веpшин, до которой дошел фронт волны, назовем вершиной фронта.
Все вершины, имеющие связи с вершиной фронта, будем называть следующий вершиной.
Если у следующей вершины поле "prev" равно "null",
то в ней полю "prev" присваивается адрес вершины фронта.
Поиск ведется до тех пор, пока волна не дойдет до конечной вершины или
пока не будут исчерпаны все вершины.
tab.from -> point.(bond/p1:p2.point[prev=null prev^^])*||id=tab.to;
Если поле "prev" последней вершины не равно "null", то путь в графе существует,
и один из путей закодирован в значениях полей "prev".
Выведем этот путь.
tab.to -> point[prev≠null] ?{
tab.from -> point[#prev].(#bond/p1:p2.point[#prev=^^])*||id=tab.to
} {{
'<p>Pass does not exist</p>'
}};
<point id="3">
<point id="4"
...
<point id="11"
...
</point>
</point>
Пример 3.2
Если вместо поля "prev" использовать множество "set"
(вначале не содержащее ни одной записи),
то в него можно записать точки фронта,
первыми одновременно достигшие данного узла
(для обнаружения одновременности введено поле дискретного времени "moment",
равное удвоенному количеству пройденных вершин).
Это позволяет найти несколько путей в графе (если они существуют).
create table point (
id num primary key,
moment num fictional
);
create table bond (
p1 num references point (id),
p2 num references point (id)
);
create table set {
ref num references point (id),
prev num references point (id)
};
create table tab (
from num references point (id),
to num references point (id)
);
то заполнение множества будет таким
point[momentnull];
~~set;
|
-- update point set moment=null;
-- delete from set;
|
tab.from -> point.(bond/p1:p2.point[
(moment=null moment!),moment=! set/ref<+>[prev^^^]
])*||id=tab.to;
А запрос для получения многих путей выглядит так
tab.to -> point.set ?{
tab.from -> point.(bond/p1:p2.point[ set/ref{
}.prev=^^^ ])*||id=tab.to
} {{
'<p>Pass does not exist</p>'
}};
Пример 3.3
Если вместо множества "set" использовать список "list"
create table point (
id num primary key,
moment num fictional,
lnk num references list (id)
);
create table bond (
p1 num references point (id),
p2 num references point (id)
);
create table list {
id num primary key,
prev num references point (id),
next num references list (id)
};
create table tab (
from num references point (id),
to num references point (id)
);
то заполнение списка будет таким
point[momentnull];
~~list;
tab.from -> point.(bond/p1:p2.point[
moment=null list{ 1}[prev^^^] moment!,
moment=! list{$+1}[prev^^^]
])*||id=tab.to;
А запрос для получения многих путей выглядит так
tab.to -> point.list ?{
tab.from -> point.(bond/p1:p2.point[ list{}[point=^^^] ])*||id=tab.to
} {{
'<p>Pass does not exist</p>'
}};
Пример 4.1
Каждая вершина, ссылаясь на другую вершину,
указывает вес связи до новой вершины (в поле "weight").
Требуется найти такой путь в графе, для которого минимальна сумма весов.
Предполагается, что в графе не существует контур отрицательного суммарного веса
(который бы позволял сделать вес пути сколь угодно малым,
"прокрутившись" в контуре необходимое количество раз.
Например, в симметричном графе
weightab=weightba,
таким контуром является любое ребро с отрицательным весом).
create table point (
id num primary key,
prev num references point (id) fictional,
sum float4 fictional
);
create table bond (
p1 num references point (id),
p2 num references point (id),
weight float4
);
create table tab (
from num references point (id),
to num references point (id)
);
Ищем путь
point[prevnull sumnull];
tab.from -> point.(bond/p1:p2.point[
sum=null, sum>^^.sum+^.weight
prev^^ sum^^.sum+^.weight ])*||id=tab.to;
Извлекается путь выражением из примера 3.1.
Пример 4.2
Если вместо поля "prev" использовать множество "set"
create table point (
id num primary key,
moment num fictional,
sum float4 fictional
);
create table bond (
p1 num references point (id),
p2 num references point (id),
weight float4
);
create table set {
ref num references point (id),
prev num references point (id)
};
create table tab (
from num references point (id),
to num references point (id)
);
то заполнение множества будет таким
point[momentnull];
~~set;
tab.from -> point.(bond/p1:p2.point[
(moment=null
set/ref<+>[prev^^^] moment! ),
(sum>^^^.sum+^^.weight, sum=^^^.sum+^^.weight moment>!
~~set
set/ref<+>[prev^^^] sum^^^.sum+^^.weight moment! ),
(sum=^^^.sum+^^.weight moment=!
set/ref<+>[prev^^^] )
])*||id=tab.to;
Извлекается путь выражением из примера 3.2.
Пример 4.3
Если вместо множества "set" использовать список "list"
create table point (
id num primary key,
moment num fictional,
lnk num references list (id),
sum float4 fictional
);
create table bond (
p1 num references point (id),
p2 num references point (id),
weight float4
);
create table list {
id num primary key,
prev num references point (id),
next num references list (id)
};
create table tab (
from num references point (id),
to num references point (id)
);
Ищем путь
point[momentnull];
~~list;
tab.from -> point.(bond/p1:p2.point[
(sum=null, sum>^^^.sum+^^.weight, sum=^^^.sum+^^.weight moment>!
~~list list{1}[prev^^^] sum^^^.sum+^^.weight moment!),
(sum=^^^.sum+^^.weight moment=! list{$+1}[prev^^^])
])*||id=tab.to;
Извлекается путь выражением из примера 3.3.
Тюрин Дмитрий
Сайт управляется системой
uCoz