www.xdb2.com/Example/Ex112.asp demos how to represent things needed to
calculate the cost of traveling between any two towns via multiple
paths. The example allows the path between any two towns to be uni or
bi-directional. The example allows the specification of travel cost
during any time period of each weekday.

More specifically, the example represents the following things: Four
towns named a, b, c, d (imagine them forming a square). There are
paths from a to b, b to c, c to d and d to a. There are also opposite
paths from a to d, d to c, c to b and b to a. In addition, there are
two uni-directional cross paths, one from a to c and the second from b
to d. The cost of travel from town a to town b on Monday between 00:00
and 24:00 is 1.00.

The script below stores above things:

// Create towns a, b, c, d
CREATE2 *town.cls = thing;
CREATE2 *a.cls = town;
CREATE2 *b.cls = town;
CREATE2 *c.cls = town;
CREATE2 *d.cls = town;

// Create directional verb "to"
// which leads to lower level (aka creature)
CREATE2 *goto.cls = verb;
CREATE2 goto.vbType = cr;

// Create a square shaped graph
// Note: outer paths are bi-dir
CREATE2 a.goto = b;
CREATE2 b.goto = a;

CREATE2 b.goto = c;
CREATE2 c.goto = b;

CREATE2 c.goto = d;
CREATE2 d.to = c;

CREATE2 d.goto = a;
CREATE2 a.goto = d;

// Note: inner cross paths are uni-dir
CREATE2 a.goto = c;
CREATE2 b.goto = d;

// Create weekdays
CREATE2 *weekday.cls = thing;

// Create start time of day (inclusive)
CREATE2 *start.cls = thing;

// Create end time of day (exclusive)
CREATE2 *end.cls = thing;

// Create costs
CREATE2 *cost.cls = thing;

// Create it cost 1.00 to go from town a to town b
// on monday between 00:00 and 24:00
CREATE2 (a.goto=b).weekday = +monday;
CREATE2 ((a.goto=b).weekday=monday).start = +00:00;
CREATE2 (((a.goto=b).weekday=monday).start=00:00).end = +24:00;
CREATE2 ((((a.goto=b).weekday=monday).start=00:00).end=24: 00).cost =
+1.00;

neo55592 (AT) hotmail (DOT) com (Neo) wrote in message news:<4b45d3ad.0411071807.4cbd51f0 (AT) posting (DOT) google.com>...
Incomplete problem description. What is the costs for travel on other
days?

Documentation error. you actually created the verb "goto"

Compile error. no such method as "to"
Actually all the so-called paths are unidirectional. You never created
a bidirectional "goto" verb.

weird operators.
Based on above, is there such a thing as a negative monday? -monday.

OR does it work like C so =+ means to add/insert/concatenate the
values? In which case how do you diferentiate between straight
replacement when the programmer wishes to emphasize the signed value
(x=+1 "x equals a positive one") versus the addition operation (x=+1
"x incremented by one <unsigned>)?



Now that you have a design, what problems do you think you can solve
with it?
(You are not really so uninformed as to suggest this might solve the
travelling salesman problem, are you?)

ed

I do not assert the script to create the db does not have redundant
things. I do assert that there are no redundant things in the db
including the word "monday" and the symbols a, b, c, d. Example
www.xdb2.com/Example/BoxProperties.asp demonstrates this ability by
displaying the ID of symbol 1 and the quantity 1. I am surprised you
didn't understand this as it was discussed and demonstrated at great
length in the recent comp.database.theory thread titled "A
Normalization Question" to which you were a significant contributor.
Would you like to reverify step-by-step that there is only one word
"monday" in the db?

Could you specify the program code that Neo stored as data. It appears
you are against storing program code as data. Could you first define
the fundamental difference between code and data. Could you then
indicate why you are against storing "code" as data. Are you asserting
that by storing the same things in a relational db, there would be no
storing of program code as data?

Could you please define what is an "object" and "object-orientation".
In RM, tables, row, columns, values can be thought of as objects. Are
you asserting that in the tools that you use, you are not practicing
some level of object-orientation?

Why don't we find out for sure. Would you be willing to model 64 towns
with various paths, cost factors and valid durations in a week; and
then query/code solutions to some typical problems to guage each
methods advantages/disadvantages? You may use RM or any other tool
that you prefer.

Please teach Neo the common sense meaning of integrity and honesty by
showing that Hugo's RM Solution #1 and #2 aren't nearly twice as slow
as XDb1's even when XDb1 is executed on a 5.6X slower machine. See
measurements below. You are weclome to download XDb1 (see
www.xdb1/example/ex076.asp) and verify it against Hugo's solutions.

Not only are Hugo's solutions slower, but they are not as generic or
normalized. For instance, Hugo's solution cannot represent the
following cases without NULLs or redundant data (XDb1's solution is
normalized down to atomic symbols):

Case1: God is the parent of an unnamed person. God is also the parent
of second person with three names (string 'john', integer 100, decimal
3.14).

Case2: john isa person. john's color is brown. mary isa person. mary's
color is brown. brown is a person.

As shown by the measurements made below, even when executed on a 5.6
times slower 233 Mhz Pocket PC, XDb1 generated the small common
ancestor report nearly twice as fast as Hugo's non-normalized,
non-generic SQL Server 2000 Solution running on a 1,300 MHz desktop.

Small Report Generation Summary (provided by Hugo)
---------------------------------------------------------------------
Solution Time(ms) Platform Notes
-------------- -------- ----------------- --------------------------
RM#1 SqlSrvr2K 14.3 1.3 Ghz PC Unnormalized, non-generic
RM#2 SqlSrvr2K 11.0 1.3 Ghz PC Unnormalized, non-generic


Small Report Generation Summary (provided by Neo)
---------------------------------------------------------------------
Solution Time(ms) Platform Notes
------------- -------- ----------------- --------------------------
RM#1 SqlSrvr7 65.0 500 Mhz Server Unnormalized, non-generic
RM#2 SqlSrvr7 68.9 500 Mhz Server Unnormalized, non-generic
XDb1 4.5.7 1.632 500 Mhz Server Normalized, generic
XDb1 4.5.9 6.561 233 MHz PocketPC Normalized, generic


Large Report (28,940 rows) Generation Summary (provided by Neo)
200 Goat Hierarchy (5 generations x 40 goats/generation,
each goat having two parents, except 1st gen).
---------------------------------------------------------------------
Solution Time(sec) Platform Notes
------------- -------- ----------------- --------------------------
RM#5 SqlSrvr7 40.5 500 Mhz Server Unnormalized, non-generic
XDb1 4.5.7 2.9 500 Mhz Server Normalized, generic
XDb1 4.5.9 16.971 233 Mhz PocketPC Normalized, generic


Larger Report (276,620 rows) Generation Summary (provided by Neo).
400 Goat Hierarchy (10 gen x 40 goats/gen),
---------------------------------------------------------------------
Solution Time(ms) Platform Notes
------------- -------- ----------------- --------------------------
RM#5 SqlSrvr7 105 min 500 Mhz Srvr, NT Avg of 2 runs, UnNrm,UnGen
XDb1 4.5.10 44 min 500 Mhz Srvr, NT Avg of 2 runs, Norm, gener
XDb1 4.5.10 57 min 450 Mhz PC, 98 1 run, Normalized, generic
XDb1 4.5.10 195 min 233 Mhz PocketPC 1 run, Normalized, generic

"Neo" <neo55592 (AT) hotmail (DOT) com> wrote

No, I believe you.

This was discussed some months ago with Dawn. No need to do it again.

I was just making a comment. It seems you interpreted it as a criticism.
Some tools (like Windows) are based on OO concepts. Others (like SQL) are
not.

No, because I do not want to get said headache and carpal tunnel syndrome.
Why don't you do it? All 64 towns. WIth a minimum of 4096 possibilities.

You may use RM or any other tool
I have no interest in attempting to solve this problem, just in pointing out
that your "solution" is not a solution, and is bound to send anyone who
tries it to the doctor.


I don't have to. It's been done. Repeatedly. You are a sore loser, and have
no integrity. Your word is worthless.

"Neo" <neo55592 (AT) hotmail (DOT) com> wrote

Why does Neo often refer to Neo in the third person?

Again.

neo55592 (AT) hotmail (DOT) com (Neo) wrote:

[snip]

Is anyone up to the challenge?

Note that I am not offering $1000 only to snatch it away by
changing the terms. You will have my admiration though, and Hugo will
have his money.

[snip]

Sincerely,

Gene Wirchenko

Computerese Irregular Verb Conjugation:
I have preferences.
You have biases.
He/She has prejudices.

paths from a to b, b to c, c to d and d to a. There are also opposite
paths from a to d, d to c, c to b and b to a. In addition, there are
two uni-directional cross paths, one from a to c and the second from b
to d. The cost of travel from town a to town b on Monday between 00:00
and 24:00 is 1.00. <<

There is no such time as 24:00 Hrs; read ISO-8601. This is pretty
straight forward in SQL.

CREATE TABLE Trips
(source_town CHAR(10) NOT NULL
REFERENCES Towns(town_name)
ON UPDATE CASCADE
ON DELETE CASCADE,
destination_town CHAR(10) NOT NULL
REFERENCES Towns(town_name)
ON UPDATE CASCADE
ON DELETE CASCADE,
travel_cost INTEGER DEFAULT 0 NOT NULL
CHECK (travel_cost >= 0),
start_time TIMESTAMP NOT NULL,
end_time TIMESTAMP NOT NULL,
CHECK (start_time < end_time),
..);


INSERT INTO Trips VALUES ('a', 'b', 1, '2004-11-08 00:00:00'
'2004-11-09 00:00:00');
INSERT INTO Trips VALUES ('b', 'c', 1, '2004-11-08 00:00:00'
'2004-11-09 00:00:00');
....
-- reverse paths
INSERT INTO Trips VALUES ('b', 'a', 1, '2004-11-08 00:00:00'
'2004-11-09 00:00:00');
INSERT INTO Trips VALUES ('c', 'b', 1, '2004-11-08 00:00:00'
'2004-11-09 00:00:00');
...
--diagonal paths
INSERT INTO Trips VALUES ('a', 'c', 1, '2004-11-08 00:00:00'
'2004-11-09 00:00:00');
INSERT INTO Trips VALUES ('b', 'd', 1, '2004-11-08 00:00:00'
'2004-11-09 00:00:00');

That gets all the (travel_cost = 1) edges in the graph. Next, use
Warshall's algorithm to fill in travel costs on ('c', 'a'), ('d', 'b')
and so forth. This will work for any adjacency list model. I would
do the matrix multiplications in a host language like FORTRAN, C or
Pascal, but I can do it in pure SQL if I have to (see that section in
SQL FOR SMARTIES).

"--CELKO--" <jcelko212 (AT) earthlink (DOT) net> wrote

Matrix product is indeed a nice relational expression (with aggregation and
grouping). That would take care of the 2 inner loops in the Warshall's
algorithm. What about the outer loop?

From another perspective, given graph adjacency matrix A, transitive closure
graph could be expressed by adjacency matrix TA like this:

TA = 1 + A + A^2 + A^3 + ...

In theory, there is an infinite sum on the right side. In practice, A is
finite dimensional so that we can stop after n steps.

The above expression uses + sign. This means that adjacency matrix
definition should be extended in order to allow integers greater than 1. As
usual, value > 0 is interpreted as a directed link between the nodes, 0
being no such link.

The formal expression containing infinite sum is appealing because it
formally equals to

(1-A)^(-1)

That's right, transitive closure could be computed as an inverse matrix.
Next, inverse matrix is just a ratio of 2 determinants. The question then is
if determinant or invers matrix calculation can be carried over in
relational algebra (with aggregation). I asked Leonid Libkin this question
some time ago, and his answer was resound "no".

In order to keep the example simple, the script only showed the cost
of travel between two towns (a to b) in one direction during a
specific day of the week (monday), during a specific time period
(00:00 to 24:00). The updated script at the end has 4 such entries and
should allow one to deduce how to enter additional ones. If you or the
original problem poster would like to present more representative
data, I can enter it.

Thanks.

Thanks! for spotting the semantic (but not syntatic) error. I
originally created the script using "to" instead of "goto", but later
realized that since the db already has the preposition "to", I would
need to use the expression (%.cls=verb & %.name=to) in order to
distinguish them making the script longer. During the conversion from
"to" to "goto" I made the above significant error.

Didn't need to create a bi-directional verb because two opposite
uni-directionals paths form a bi-directional path as in:
CREATE2 a.goto = b;
CREATE2 b.goto = a;

If I had created a bi-directional verb, it would be difficult to
specify a one way street and different cost/period for each
uni-direction.

The + indicates that if monday does not already exist as an instance
of the verb (weekday), go ahead and create it. The above script is
equivalent to below which doesn't use the "+" sign:

CREATE2 *; // aka it
CREATE2 it.name = monday; // short cut to relating to each symbol
CREATE2 it.cls = weekday;
CREATE2 (a.goto=b).weekday = monday; // or "(a.goto=b).weekday = it;"

I am open to suggestions for improving XDb2's scripting language.

I assumed that people would understand the example only represents the
things needed in a db to calculate best path and not the algorithms to
do so. However I believe I could code the algorithm. Are you saying
that no one has solved this type of problem with RM thus far?

----------------------------
Below is the updated script:

// Create towns a, b, c, d
CREATE2 *town.cls = thing;
CREATE2 *a.cls = town;
CREATE2 *b.cls = town;
CREATE2 *c.cls = town;
CREATE2 *d.cls = town;

// Create uni-directional verb "goto"
// which leads to lower level (aka creature)
CREATE2 *goto.cls = verb;
CREATE2 goto.vbType = cr;

// Create a square shaped graph
// Note: outer paths are bi-dir
CREATE2 a.goto = b;
CREATE2 b.goto = a;

CREATE2 b.goto = c;
CREATE2 c.goto = b;

CREATE2 c.goto = d;
CREATE2 d.goto = c;

CREATE2 d.goto = a;
CREATE2 a.goto = d;

// Note: inner cross paths are uni-dir
CREATE2 a.goto = c;
CREATE2 b.goto = d;

// Create weekdays
CREATE2 *weekday.cls = thing;

// Create start time of day (inclusive)
CREATE2 *start.cls = thing;

// Create end time of day (exclusive)
CREATE2 *end.cls = thing;

// Create costs
CREATE2 *cost.cls = thing;

// Create it cost 1.00 to go from town a to town b
// on monday between 00:00 and 24:00
CREATE2 (a.goto=b).weekday = +monday;
CREATE2 ((a.goto=b).weekday=monday).start = +00:00;
CREATE2 (((a.goto=b).weekday=monday).start=00:00).end = +24:00;
CREATE2 ((((a.goto=b).weekday=monday).start=00:00).end=24: 00).cost =
+1.00;

// Create it cost 1.56 to go from town b to town a
// on tuesday between 08:00 and 17:00
CREATE2 (b.goto=a).weekday = +tuesday;
CREATE2 ((b.goto=a).weekday=tuesday).start = +08:00;
CREATE2 (((b.goto=a).weekday=tuesday).start=08:00).end = +17:00;
CREATE2 ((((b.goto=a).weekday=tuesday).start=08:00).end=17 :00).cost =
+1.56;

// Create it cost 2.30 to go from town b to town c
// on wednesday between 09:00 and 15:00
CREATE2 (b.goto=c).weekday = +wednesday;
CREATE2 ((b.goto=c).weekday=wednesday).start = +09:00;
CREATE2 (((b.goto=c).weekday=wednesday).start=09:00).end = +15:00;
CREATE2 ((((b.goto=c).weekday=wednesday).start=09:00).end= 15:00).cost
= +2.30;

// Create it cost 3.16 to go from town c to town b
// on thursday between 10:00 and 14:00
CREATE2 (c.goto=b).weekday = +thursday;
CREATE2 ((c.goto=b).weekday=thursday).start = +10:00;
CREATE2 (((c.goto=b).weekday=thursday).start=10:00).end = +14:00;
CREATE2 ((((c.goto=b).weekday=thursday).start=10:00).end=1 4:00).cost =
+3.16;

I would say nearly all tools have object-like orientation but to
different degrees including SQL.

It would be more fun to compare the methodology of several solutions.
Would any RM, OO, C++, Haskel proponent like to join? I woundn't start
with 64 towns though. The permutation of paths among 64 towns is
likely to be much bigger than 4096

You are correct, the solution only represented things and does not
provide algorithms to process those things. I didn't know I was under
that obligation. I titled the thread Modelling... not Computing...

Then how difficult could it be for you to do it again. Please post the
execution time of XDb1 vs Hugo's on your machine for the small report.
And please show how to represent case 1 or 2 without NULLs or
redundant data.