Перечень статей Терминология Choose language

Примеры

Пример 1. Выбрать сотрудников, зарплата которых выше средней в их подразделении, в порядке убывания зарплаты.

create table department {
  id         num      primary key,
  name       string
};
create table employee {
  id         num      primary key,
  name       string,
  salary     num,
  department num      references department (id)
};

Запрос слева ниже, вывод базы данных справа ниже (поле "department" таблицы "employee" не выводится, т.к. оно уже использовано при построении выходных данных).

select department.employee
  where @salary > (
    select avg(@salary)
    from   employee e
    where  e/@department=department/@id
  ) order by @salary desc;

<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. Пусть существует ряд городов, которые сообщаются рейсами некоторого транспорта без промежуточных остановок.

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
);

по каким дням недели есть прямые рейсы из города "a" в город "b"

select flight
  from city[@name="a"].flight#c1:c2.city[@name="b"];

<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">

как в понедельник добраться из города "a" в город "b" (время для пересадки не менее 30 минут)

select (flight[@t1 @t2].city)*
  from  city[@name="a"].(flight#c1:c2[@day="monday"].city)*
  where previous(flight)/@t1 - next(flight)/@t2 > 00.30
    and last(city)/@name="b";

<flight   t1="5.30"  t2="5.50">
 <city    name="C">
  <flight t1="7.00"  t2="11.00">
   <city  name="B">
  </flight>
 </city>
</flight>
<flight   t1="5.10"  t2="12.10">
 ...
  <city   name="B">
 ...
</flight>

нужно вылететь из города "a" в понедельник и вернуться в него обратно в пятницу, посетив города "b", "c", "d". В какой последовательности следует посещать города, чтобы не совершать более одного перелета в день

select  city[@name="a"].(flight#c1:c2.city[@name as @n])*
  where first(flight)/@day="monday"
    and last(flight)/@day="friday"
    and @n in ("b", "c", "d", "a")
    and previous(flight)/@t1 - next(flight)/@t2 > 00.30
    and last(city)/@name="a"

<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. Пусть мы ищем в графе путь, проходящий через минимальное количество вершин. Каждая вершина есть запись в таблице "point". Связи между вершинами хранятся в таблице "bond". Путь ищется из вершины, первичный ключ которой задан в поле "tab.from" (начальная вершина), к вершине, первичный ключ которой задан в поле "tab.to" (конечная вершина), таблица "tab" имеет единственную запись.

create table point (
  id     num primary key,
  moment num
);
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)
);

Переберем все вершины от начальной к конечной - распространяется волна перебора. Каждая вершина в поле "moment" содержит момент прихода волны (момент равен удвоенному количеству пройденных вершин). Найдем все кратчайшие (с одинаковой длиной) пути в графе (если они существуют).

update point set @moment=null;
update tab#from.point.(bond#p1:p2.point[@moment=null])*.tab#to
  set  @moment=!
;
if           tab#to.point/@moment is not null
then select  point.(point)*
       from  tab#from.point.(bond#p1:p2.point[@moment=!])*.tab#to
else select "<p>Pass does not exist</p>"
;

<point    id="3">
 <point   id="4"
  ...
   <point id="11"
  ...
 </point>
</point>

Пример 4. Каждая вершина, ссылаясь на другую вершину, указывает вес связи до новой вершины (в поле "weight"). Требуется найти такой путь в графе, для которого минимальна сумма весов. Предполагается, что в графе не существует контур отрицательного суммарного веса (который бы позволял сделать вес пути сколь угодно малым, "прокрутившись" в контуре необходимое количество раз. Например, в симметричном графе weight_a_b=weight_b_a, таким контуром является любое ребро с отрицательным весом).

create table point (
  id     num primary key,
  moment num,
  total  float4
);
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)
);

Ищем путь

update point set @moment=null, @total=null;
update tab#from.point.(bond#p1:p2.point[@moment=null or @total>../../@total+./@weight])*.tab#to
  set  @moment=!, @total=../../@total+./@weight
;
if           tab#to.point/@moment is not null
then select  point.(point)*
       from  tab#from.point.(bond#p1:p2.point[@moment=! and @total=../../@total+./@weight])*.tab#to
else select "<p>Pass does not exist</p>"
;

Тюрин Дмитрий

Перечень статей Терминология Choose language