large data : how do you store multidimensional data ?

[amit]

assume we have 10,000 cities. imagine those distance calculating
tables, where city A (row) to city Z (col) would equal a float value.
city Z (row) to city Z(col) would be 0. The only problem is our table
is not A-Z with a 26x26 table. It's 10,000 x 10,000 .

How can you store this data in a sql table efficiently ?

Thanks in advance.

[amit]

sorry the above example is a 2 dimensional. not multidimensional.

[Plamen Ratchev]

This is a typical undirected cyclic graph. Each edge represents a
two-way relationship. You normally store it as pairs from_city/to_city
and the distances between the pairs. When you need to find a path
between cities you convert it to digraph where each edge becomes two
directed edges, so (cityA, cityB) becomes (cityA, cityB) and (cityB, cityA).

--
Plamen Ratchev
http://www.SQLStudio.com

[Roy Harvey (SQL Server MVP)]

On Mon, 25 Aug 2008 23:11:42 -0700 (PDT), am**@desiboy.com wrote:

>assume we have 10,000 cities. imagine those distance calculating
tables, where city A (row) to city Z (col) would equal a float value.
city Z (row) to city Z(col) would be 0. The only problem is our table
is not A-Z with a 26x26 table. It's 10,000 x 10,000 .

How can you store this data in a sql table efficiently ?

I would want the Cities table to have an INT column as the key. Then
the CityDistance table would be three columns, (CityA, CityB,
Distance), where CityA, CityB is an ordered pair, probably CityA <
CityB for the ordering. Indexing depends on how you want to access
the data.

On the other hand, if this is really cities and distances, and the
distances are direct (as opposed to by road, for example), it might be
more efficient to add latitude and longitude to the Cities table and
calculate the distance on the fly. You might want to explore the
geospatial features introduced in SQL Server 2008 in that case.

Roy Harvey
Beacon Falls, CT

[Erland Sommarskog]

Roy Harvey (SQL Server MVP) (ro********@snet.net) writes:

I would want the Cities table to have an INT column as the key. Then
the CityDistance table would be three columns, (CityA, CityB,
Distance), where CityA, CityB is an ordered pair, probably CityA <
CityB for the ordering. Indexing depends on how you want to access
the data.

I would suggest that querying is a lot easier if you store both pairs,
even if this means that it takes up twice as much as space. Also, depending
on what's actually is those tables, it can be a good idea to store
the "self-pairs" (cityA, cityA) as well.

We did something like this with exchange rates and they were stored by
day, so the table became really huge. What we did later was to identify
that were a lot of exchange rates that no one would ever query about.
So we added a flag on currencies to mark them as "important" and then
we only saved and computed FX rates that involved at least on important
currency. (All self-pairs were still included.) I mention this, in case
it's applicable to Amit's business problem.
--
Erland Sommarskog, SQL Server MVP, es****@sommarskog.se

Links for SQL Server Books Online:
SQL 2008: http://msdn.microsoft.com/en-us/sqlserver/cc514207.aspx
SQL 2005: http://msdn.microsoft.com/en-us/sqlserver/bb895970.aspx
SQL 2000: http://www.microsoft.com/sql/prodinf...ons/books.mspx

[--CELKO--]

On Aug 26, 1:11 am, [e-mail] wrote:

assume we have 10,000 cities. imagine those distance calculating
tables, where city A (row) to city Z (col) would equal a float value.
city Z (row) to city Z(col) would be 0. The only problem is our table
is not A-Z with a 26x26 table. It's 10,000 x 10,000 .

How can you store this data in a sql table efficiently ?

Thanks in advance.

1) If you really want the distance as a column in the table, then:

CREATE TABLE OneWayTrips
(first_city_code INTEGER NOT NULL,
second_city_code INTEGER NOT NULL,
distance FLOAT NOT NULL,
CHECK (first_city_code < second_city_code) ,
PRIMARY KEY (first_city_code, second_city_code) );

Now do everything off of a VIEW with an INSTEAD OF TRIGGER for
insertions, and updates and deletes.

CREATE VIEW Trips (first_city_code, second_city_code, distance)
AS
SELECT first_city_code, second_city_code, distance
FROM OneWayTrips
UNION ALL
SELECT second_city_code, first_city_code, distance
FROM OneWayTrips
UNION ALL
SELECT first_city_code, first_city_code, 0.00
FROM OneWayTrips
UNION ALL
SELECT second_city_code, second_city_code, distance
FROM OneWayTrips;

2) Otherwise:

CREATE TABLE Cities
(city_code INTEGER NOT NULL PRIMARY KEY,
longitude FLOAT NOT NULL,
latitude FLOAT NOT NULL);

Compute the distance with the usual formulas.