Spatial Location Code
Een oplossing voor het efficiënter opslaan en opzoeken
van ruimtelijke objecten in grote databases
NGT GEODESIA
1996-6
gis/lis, data structures, theory
gis/lis, gegevensstructuren, theorie
KEYWORDS
TREFWOORDEN
Dit artikel beschrijft de Spatial Location Code (SLC) die
gebruikt kan worden voor het indexeren en clusteren
van geografische objecten in een database. Deze code
combineert de sterke aspecten van enkele bekende
ruimtelijke zoekmethoden (Quadtree, Field-tree en
Morton-waarde) tot één enkele SLC-waarde per object.
De unieke eigenschap van de SLC is dat zowel de locatie
als de grootte van objecten (mogelijk met een omvang,
dus niet alleen puntobjecten) worden benaderd door
deze enkele waarde. De zo verkregen SLC-waarden
kunnen vervolgens worden gebruikt in combinatie met
een traditionele zoekmethode, zoals de B-tree, beschik
baar in iedere database. Hierdoor wordt de responsetijd
bij ruimtelijke zoekopdrachten voor omvangrijke
gegevensverzamelingen vele malen verminderd.
De voorbeelden in dit artikel zijn beschreven in een
tweedimensionale ruimte, maar de SLC-methode is
algemeen en kan ook worden toegepast in hogere
dimensies.
De SLC is ontworpen om het efficiënt
opslaan en opzoeken van ruimtelijke
gegevens in een standaard (relationele)
DBMS (DataBase Management Sys
teem) mogelijk te maken. De ont
werpeisen voor de SLC worden hier
onder kort samengevat:
geschikt voor tenminste tweedimen
sionale gegevens;
snel gegevens binnen een opgegeven
rechthoek kunnen vinden door
middel van het toepassen van ruim
telijke clustering en indexering;
slechts één waarde per object in
plaats van een verzameling waarden
per object, omdat dit lastig is bij ge
bruik van een DBMS;
zo transparant mogelijk voor wat
betreft het datamodel en de vra-
gen;
geen DBMS kernei-veranderingen
vereisen, dat wil zeggen gebruik maken
gegevenstypen en zoekmethoden.
/an standaard
dr. ir. P. van Oosterom*), Kadaster,
Concernstraf Vastgoedinformatie en
Landinrichting te Apeldoorn en
ir. T. Vijlbrief, TNO Technische
Menskunde te Soesterberg.
1 Dit werk is gedeeltelijk uitgevoerd in de periode
dat de auteur in dienst was bij het TNO Fysisch
en Elektronisch Laboratorium in Den Haag.
Daar de oplossing implementeerbaar moet zijn binnen elke
DBMS-omgeving, is de SLC-uitbreiding gebaseerd op een
bestaand gegevenstype (bijvoorbeeld integerd) in combina
tie met een bestaande zoekmethode, zoals de B-tree [4],
Een globale schets van de ontworpen oplossing is dan:
Voeg een SLC-attribuut toe aan elke tabel in de database
waarin een ruimtelijk gegevenstype voorkomt (point,
line, polygon of box). De SLC is een ééndimensionale
waarde en elk object krijgt precies één waarde. Deze
waarde benadert zowel de positie als de grootte van objec
ten. Het is mogelijk dat twee verschillende objecten door
dezelfde SLC-waarde worden benaderd, maar dan heb
ben deze objecten ongeveer dezelfde grootte en dezelfde
positie.
Modificeer de structuur tot een B-tree gelijkende tabel op
het SLC-attribuut. Dit zorgt ervoor dat de objecten min
of meer worden opgeslagen in de
volgorde bepaald door de B-tree.
Deze primaire index is verantwoor
delijk voor de ruimtelijke clustering.
Definieer twee functies:
a. Compute_SLC: berekent de
SLC-waarde van een tweedimen
sionale rechthoek. Eerst wordt
van een object de kleinst omhul
lende rechthoek bepaald en ver
volgens de SLC van deze recht
hoek. Er is dus maar één Com-
pute_SLC functie nodig;
b. Overlap_SLC: bepaalt de SLC-
intervallen die de gegeven
tweedimensionale zoekrechthoek
overlappen.
Tenslotte kunnen we regels en pro
cedures binnen de DBMS defini
ëren om de SLC transparant te ma
ken voor de gebruiker:
a. vul het SLC-attribuut ingeval
243
