Skip to main content
Erschienen in: GeoInformatica 1/2010

01.01.2010

User defined topological predicates in database systems

verfasst von: Thomas Behr, Ralf Hartmut Güting

Erschienen in: GeoInformatica | Ausgabe 1/2010

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

Current database systems cannot only store standard data like \(\underline{integer}\), \(\underline{string}\), and \(\underline{real}\) values, but also spatial data like \(\underline{points}\), \(\underline{lines}\), and \(\underline{regions}\). The importance of topological relationships between spatial objects has been recognized a long time ago. Using the well known 9-intersection model for describing such relationships, a lot of different topological relationships can be distinguished. For the query language of a database system it is not desirable to have such a large number of topological predicates. Particularly the query language should not be extended by a lot of predicate names. It is desirable to build new relationships from existing ones, for example to coarse the granularity. This paper describes how a database system user can define and use her own topological predicates. We show algorithms for computing such predicates in an efficient way. Last, we compare these general versions with specialized implementations of topological predicates.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Anhänge
Nur mit Berechtigung zugänglich
Fußnoten
1
A complex line may consist of several non-connected parts, and may have any number of endpoints (also zero for a loop.)
 
2
For technical reasons, in Secondo’s SQL-like query language, names of objects (relations) and attributes are written in lower case.
 
3
The standard predicate also calls the toppred operator using a predefined object of type \(\underline{cluster}\).
 
Literatur
1.
Zurück zum Zitat Clementini E, di Felice P (1996) A model for representing topological relationships between complex geometric features in spatial databases. Inf Sci 90(1–4):121–136CrossRef Clementini E, di Felice P (1996) A model for representing topological relationships between complex geometric features in spatial databases. Inf Sci 90(1–4):121–136CrossRef
2.
Zurück zum Zitat Clementini E, Di Felice P, Califano G (1995) Composite regions in topological queries. IS 20(7):579–594 Clementini E, Di Felice P, Califano G (1995) Composite regions in topological queries. IS 20(7):579–594
3.
Zurück zum Zitat Clementini E, Felice PD (1993) An object calculus for geographic databases. In: SAC ’93: Proceedings of the 1993 ACM/SIGAPP symposium on applied computing. New York, NY, USA, ACM, pp 302–308CrossRef Clementini E, Felice PD (1993) An object calculus for geographic databases. In: SAC ’93: Proceedings of the 1993 ACM/SIGAPP symposium on applied computing. New York, NY, USA, ACM, pp 302–308CrossRef
4.
Zurück zum Zitat Clementini E, Felice PD, van Oosterom P (1993) A small set of formal topological relationships suitable for end-user interaction. In: SSD: advances in spatial databases. LNCS, Springer Clementini E, Felice PD, van Oosterom P (1993) A small set of formal topological relationships suitable for end-user interaction. In: SSD: advances in spatial databases. LNCS, Springer
5.
Zurück zum Zitat Egenhofer M, Clementini E, Di Felice P (1994) Topological relations between regions with holes. Int J Geographic Inf Syst 8(2):128–142 Egenhofer M, Clementini E, Di Felice P (1994) Topological relations between regions with holes. Int J Geographic Inf Syst 8(2):128–142
6.
Zurück zum Zitat Egenhofer MJ (1989) A formal definition of binary topological relationships. In: Litwin W, Schek H (eds) Third international conference on foundations of data organization and algorithms (FODO). Lecture Notes in Computer Science, vol 367. Springer, pp 457–472, June Egenhofer MJ (1989) A formal definition of binary topological relationships. In: Litwin W, Schek H (eds) Third international conference on foundations of data organization and algorithms (FODO). Lecture Notes in Computer Science, vol 367. Springer, pp 457–472, June
7.
Zurück zum Zitat Egenhofer MJ, Herring JR (1990) Categorizing binary topological relations between regions, lines, and points in geographic databases. Technical report, Department of Surveying Engineering, University of Maine, Maine Egenhofer MJ, Herring JR (1990) Categorizing binary topological relations between regions, lines, and points in geographic databases. Technical report, Department of Surveying Engineering, University of Maine, Maine
8.
Zurück zum Zitat Gaal SA (1964) Point set topology. Academic, New York Gaal SA (1964) Point set topology. Academic, New York
9.
Zurück zum Zitat Güting RH (1993) Second-order signature: a tool for specifying data models, query processing, and optimization. In: Proc. of the ACM SIGMOD international conf. on management of data, pp 277–286 Güting RH (1993) Second-order signature: a tool for specifying data models, query processing, and optimization. In: Proc. of the ACM SIGMOD international conf. on management of data, pp 277–286
10.
Zurück zum Zitat Güting RH, Behr T, Almeida V, Ding Z, Hoffmann F, Spiekermann M (2004) SECONDO: an extensible dbms architecture and prototype. Technical report, FernUniversität Hagen Güting RH, Behr T, Almeida V, Ding Z, Hoffmann F, Spiekermann M (2004) SECONDO: an extensible dbms architecture and prototype. Technical report, FernUniversität Hagen
11.
Zurück zum Zitat Güting RH, de Almeida VT, Ansorge D, Behr T, Ding Z, Höse T, Hoffmann F, Spiekermann M, Telle U (2005) SECONDO: an extensible dbms platform for research prototyping and teaching. In: ICDE. IEEE Computer Society, pp 1115–1116 Güting RH, de Almeida VT, Ansorge D, Behr T, Ding Z, Höse T, Hoffmann F, Spiekermann M, Telle U (2005) SECONDO: an extensible dbms platform for research prototyping and teaching. In: ICDE. IEEE Computer Society, pp 1115–1116
12.
Zurück zum Zitat Güting RH, Ding Z (2004) A simple but effective improvement to the plumb-line algoritm. Inf Process Lett 91(6):251–257CrossRef Güting RH, Ding Z (2004) A simple but effective improvement to the plumb-line algoritm. Inf Process Lett 91(6):251–257CrossRef
13.
Zurück zum Zitat Güting RH, Schneider M (1995) Realm-based spatial data types: the ROSE algebra. VLDB J 4(2):243–286CrossRef Güting RH, Schneider M (1995) Realm-based spatial data types: the ROSE algebra. VLDB J 4(2):243–286CrossRef
14.
Zurück zum Zitat Kothuri R, Godfrind A, Beinat E (2007) Pro oracle spatial for oracle database 11g. Springer, New York Kothuri R, Godfrind A, Beinat E (2007) Pro oracle spatial for oracle database 11g. Springer, New York
15.
Zurück zum Zitat Open GIS Consortium, Inc. (1999) OpenGIS simple features specification for SQL Revision 1.1, OpenGIS Project Document 99-049, May Open GIS Consortium, Inc. (1999) OpenGIS simple features specification for SQL Revision 1.1, OpenGIS Project Document 99-049, May
17.
Zurück zum Zitat Reasey Praing MS (2008) Efficient implementation techniques for topological predicates on complex spatial objects. GeoInformatica 12(3):313–356CrossRef Reasey Praing MS (2008) Efficient implementation techniques for topological predicates on complex spatial objects. GeoInformatica 12(3):313–356CrossRef
18.
Zurück zum Zitat Schneider M (2002) Implementing topological predicates for complex regions. In: Proceedings of the international symposium on spatial data handling, pp 313–328 Schneider M (2002) Implementing topological predicates for complex regions. In: Proceedings of the international symposium on spatial data handling, pp 313–328
19.
Zurück zum Zitat Schneider M (2004) Computing the topological relationship of complex regions. In: DEXA, pp 844–853 Schneider M (2004) Computing the topological relationship of complex regions. In: DEXA, pp 844–853
20.
Zurück zum Zitat Schneider M, Behr T (2006) Topological relationships between complex spatial objects. ACM Trans Database Syst 31(1):39–81CrossRef Schneider M, Behr T (2006) Topological relationships between complex spatial objects. ACM Trans Database Syst 31(1):39–81CrossRef
21.
Zurück zum Zitat Shamos MI, Hoey D (1976) Geometric intersection problems. In: FOCS. IEEE, pp 208–215 Shamos MI, Hoey D (1976) Geometric intersection problems. In: FOCS. IEEE, pp 208–215
22.
Zurück zum Zitat Stonebraker M, Frew J, Gardels K, Meredith J (1993) The sequoia 2000 benchmark. In: Buneman P, Jajodia S (eds) Proceedings of the 1993 ACM SIGMOD international conference on management of data. Washington, D.C., 26–28 May, ACM, New York, pp 2–11CrossRef Stonebraker M, Frew J, Gardels K, Meredith J (1993) The sequoia 2000 benchmark. In: Buneman P, Jajodia S (eds) Proceedings of the 1993 ACM SIGMOD international conference on management of data. Washington, D.C., 26–28 May, ACM, New York, pp 2–11CrossRef
Metadaten
Titel
User defined topological predicates in database systems
verfasst von
Thomas Behr
Ralf Hartmut Güting
Publikationsdatum
01.01.2010
Verlag
Springer US
Erschienen in
GeoInformatica / Ausgabe 1/2010
Print ISSN: 1384-6175
Elektronische ISSN: 1573-7624
DOI
https://doi.org/10.1007/s10707-008-0075-y

Weitere Artikel der Ausgabe 1/2010

GeoInformatica 1/2010 Zur Ausgabe