Het onderhouden van connectiviteit in ruimtelijke gegevens

Abstract

Deze masterproef heeft als doel een FOIES (first order incremental evaluation system) te construeren voor de topologische connectiviteit van ruimtelijke gegevens. De verschillende domeinen die nodig zijn voor het onderzoek worden eerst uitvoerig besproken en later gecombineerd om zo te komen tot het feitelijke onderzoek. Relationele databases en eerste orde logica worden gedefinieerd en besproken. Het principe van FOIES wordt uitvoerig uitgelegd en precies gedefinieerd. De constructie van een FOIES voor de transitieve sluiting van ongerichte grafen door Patnaïk en Immerman (die werkt m.b.v. een spanning forest) wordt volledig uit de doeken gedaan. De tekortkomingen van de constructie worden weggewerkt en aangevuld en correctheid van de uiteindelijke constructie zijn wordt aangetoond. Vervolgens wordt er een licht geworpen op constraint databases: ook hier worden de basisdefinities vastgelegd en de grondbeginselen goed uitgelegd. De belangrijke natural active collapse stelling wordt besproken en het principe van de implementatie van constraint databases wordt uitgelegd. Tenslotte wordt er ook nog het begrip van topologische connectiviteit gedefinieerd alvorens er overgegaan wordt tot het zoeken naar een FOIES. Hier wordt tevens ineens aangetoond dat topologische connectiviteit niet rechtstreeks uitdrukbaar is in FO. Nadat deze domeinen uitvoerig besproken zijn, wordt er gefocust op het zoeken naar een FOIES om topologische connectiviteit incrementeel en decrementeel te berekenen. Er wordt op basis van de constructie van Patnaik en Immerman een FOIES geconstrueerd die de topologische connectiviteit van lijnstukken uitdrukt. De constructie is volledig FO incrementeel definieerbaar, maar is decrementeel niet sluitend. Er wordt een korte automatisatie ingevoerd die a.d.h.v. het aantal snijdende lijnstukken (met het te verwijderen lijnstuk) een formule selecteert die de update dan wel in FO kan volbrengen. Doch deze constructie is geen volledige FOIES. Tenslotte wordt er geëindigd met de vaststelling dat de constructie voor lijnstukken enkel gebruik maakt van de snijdende eigenschap, waardoor het vermoeden ontstaat dat de constructie gemakkelijk uitbreidbaar is naar parametriseerbare krommen.