Elementary algorithm is wave algorithm
Examples
Example 1.
Select employee, salary of which above average salary in their department,
in order of decreasing of their salary.
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)
};
Request is so:
department.employee[^.sum
^.sum+salary ^.amount^.amount+1];
department[#sum #amount].employee[-1salary>^.sum/^.amount] 
;
Database make the following output
(field "department" of table "employee" of is not in output,
because it is already used during creating output).
<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>
Example 2.
Let there are a set of cities and set of flights between them.
It's required to find:
- in what days of week there are direct flights from city "a" into city "b"
- how to reach from city "a" into city "b" on Monday
- it's necessary to flight from city "a" for Monday and to return back into it on Friday
through cities "b", "c", "d".
In what sequence it's necessary to visit cities to not make more than one flight per day
All names of cities are stored in table "city".
Next section ("flight") in tree is list of cities,
into which it's possible to flight from this city
(conditions of such possibility are presence of flight and enough time for change flight),
fields
"c1" - departure city, "t2" - arrival city,
"t1" - departure time, "t2" - arrival time,
"day" - days of week, in which flight is executed.
Address of city "a" is in a field "tab.from", address of city "b" - in a field "tab.to",
addresses of cities "b", "c", "d" are in table "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
);
Answer for first question:
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">
Answer for second question:
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>
And answer to third question looks so.
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>
Example 3.1
Let we search path in count, going through minimum quantity of nodes.
Each node is record in table "point".
Bonds between nodes is in table "bond".
Path is searched from node, primary key of which is in field "tab.from" (initial node),
to node, primary key of which is in field "tab.to" (final node),
table "tab" has one record.
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)
);
Let's look at all nodes from initial node to final node - wave goes.
Each node contains primary key of node, from which wave has come, in field "prev".
We assign "null" as initial value for all nodes.
point[prevnull];
|
-- update point set prev=null;
|
We shall name each node, to which wave front has gone, as node of front.
We shall name all nodes, having bonds with node of front, as next node.
If next node has field "prev" equal to "null",
then we assign primary key of front node into field "prev" of it.
Search go, while wave is not reach final node or
while all nodes are not searched.
tab.from -> point.(bond/p1:p2.point[prev=null prev^^])*||id=tab.to;
If field "prev" of final node is not equal "null", then path exists in count,
and one of pathes is coded in values of fields "prev".
We make output of this path.
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>
Example 3.2
If set "set" is used instead of field "prev"
(which does not contain any record in the beginning),
then it's possible to write points of wave,
which have reached this node as first simultaneously, into it
(field of discrete time "moment", equal to double quantity of gone nodes,
is used for detection a simultaneity).
It allows to find several pathes in count (if they exist).
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)
);
then filling of set is so
point[momentnull];
~~set;
|
-- update point set moment=null;
-- delete from set;
|
point[momentnull];
~~set;
tab.from -> point.(bond/p1:p2.point[
(moment=null moment!),moment=! set/ref<+>[prev^^^]
])*||id=tab.to;
And request to get much pass is so
tab.to -> point.set ?{
tab.from -> point.(bond/p1:p2.point[ set/ref{
}.prev=^^^ ])*||id=tab.to
} {{
'<p>Pass does not exist</p>'
}};
Example 3.3
If use list "list" instead set "set"
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)
);
then filling of list is so
point[momentnull];
~~list;
tab.from -> point.(bond/p1:p2.point[
moment=null list{ 1}[prev^^^] moment!,
moment=! list{$+1}[prev^^^]
])*||id=tab.to;
And request to get much pass is so
tab.to -> point.list ?{
tab.from -> point.(bond/p1:p2.point[ list{}[point=^^^] ])*||id=tab.to
} {{
'<p>Pass does not exist</p>'
}};
Example 4.1
Each node, referring to other node,
specifies weight of bond to new node (in field "weight").
It's required to find such path in count, for which sum of weights is minimal.
It's supposed, that contour with negative total weight don't exist in count
(such contour allow to make weight of path as small as you want,
"having scrolled" in contour necessary quantity of time.
For example,
weightab=weightba
in symmetric count,
any bond with negative weight is such contour).
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)
);
We search pass
point[prevnull sumnull];
tab.from -> point.(bond/p1:p2.point[
sum=null, sum>^^.sum+^.weight
prev^^ sum^^.sum+^.weight ])*||id=tab.to;
Pass is got by expression from example 3.1.
Example 4.2
If set "set" is used instead of field "prev"
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)
);
then filling of set is so
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;
Pass is got by expression from example 3.2.
Example 4.3
If use list "list" instead set "set"
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)
);
We search pass
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;
Pass is got by expression from example 3.3.
Dmitry Turin
Сайт управляется системой
uCoz