Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
GeoInformatica
Published in: GeoInformatica 1/2019

04-01-2019

Query rewriting for semantic query optimization in spatial databases

Authors: Eduardo Mella, M. Andrea Rodríguez, Loreto Bravo, Diego Gatica

Published in: GeoInformatica | Issue 1/2019

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

Query processing is an important challenge for spatial databases due to the use of complex data types that represent spatial attributes. In particular, due to the cost of spatial joins, several optimization algorithms based on indexing structures exist. The work in this paper proposes a strategy for semantic query optimization of spatial join queries. The strategy detects queries with empty results and rewrites queries to eliminate unnecessary spatial joins or to replace spatial by thematic joins. This is done automatically by analyzing the semantics imposed by the database schema through topological dependencies and topological referential integrity constraints. In this way, the strategy comes to complement current state-of-art algorithms for processing spatial join queries. The experimental evaluation with real data sets shows that the optimization strategy can achieve a decrease in the time cost of a join query using indexing structures in a spatial database management system (SDBMS).
previous article Spatial data management in apache spark: the GeoSpark perspective and beyond
next article An overlapping Voronoi diagram-based system for multi-criteria optimal location queries

Dont have a licence yet? Then find out more about our products and how to get one now:

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!

inform now

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!

inform now

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!

inform now
Footnotes
1
The names given in [9] have their equivalence in the relations in [19].
 
2
Note that PostGIS uses the name Touches instead of relation Meet.
 
Literature
1.
Popa L, Deutsch A, Tannen V (2005) Query Reformulation with Constraints
2.
Aref Walid G, Samet Hanan (1991) Optimization for spatial query processing. In: 17th international conference on very large data bases, september 3-6, 1991, barcelona, catalonia, spain, proceedings, pp 81–90
3.
Bogorny V, Engel PM, Alvares LOC (2005) Towards the reduction of spatial join for knowledge discovery in geographic databases using geo-ontologies and spatial integrity constraints. In: Proc of the ECML/PKDD second workshop on knowledge discovery and ontologies (KDO’2005), pp 51–58
4.
Bravo L, Rodríguez AM (2012) Formalization and reasoning about spatial semantic integrity constraints. Data Knowl Eng 72:63–82CrossRef
5.
Clementini E, Sharma J, Egenhofer MJ (1994) Modelling topological spatial relations: strategies for query processing. Comput Graph 18(6):815–822CrossRef
6.
Deutsch A, Ludäscher B, Nash A (2007) Rewriting queries using views with access patterns under integrity constraints. Theor Comput Sci 371(3):200–226CrossRef
7.
Deutsch A, Popa L, Tannen V (1999) Physical data independence, constraints, and optimization with universal plans. In: VLDB, pp 459–470
8.
Deutsch A, Popa L, Tannen V (2006) Query reformulation with constraints. SIGMOD Rec 35(1):65–73CrossRef
9.
Egenhofer M, Al-Taha K (1992) Reasoning about gradual change of topological relationships. In: Frank A, Campari I, Formentini U (eds) Theories and methods of spatio-temporal reasoning in geographic space, LNCS 636, Springer, pp 196–219
10.
Egenhofer MJ, Franzosa RD (1991) Point-set topological spatial relations. Int J Geogr Inf Syst 5:161–174CrossRef
11.
Egenhofer MJ, Herring J (1990) Categorizing binary topological relations between regions, lines and points in geographic databases, the 9-intersection. Formalism and its Use for Natural Language Spatial Predicates Santa Barbara CA National Center for Geographic Information and Analysis Technical Report 94:1–28
12.
Egenhofer MJ (1994) Deriving the composition of binary topological relations. J Vis Lang Comput 5(2):133–149CrossRef
13.
Grant J, Gryz J, Minker J, Raschid L (2000) Logic-based query optimization for object databases. IEEE Trans Knowl Data Eng 12(4):529–547CrossRef
14.
Jacox EH, Samet H (2007) Spatial join techniques. ACM Trans Database Syst 32(1):7CrossRef
15.
Lee SG, Henschen LJ, Chun J, Lee T (2000) Identifying relevant constraints for semantic query optimization. Inf Softw Technol 42(13):899–914CrossRef
16.
Mamoulis N, Theodoridis Y, Papadias D (2005) Spatial joins: algorithms, cost models and optimization techniques. In: Manolopoulos Y, Papadopoulos A, Vassilakopoulos M (eds) Spatial databases: technologies, techniques and trends, idea group, pp 155–184
17.
Maher MJ, Wang J (2000) Optimizing queries in extended relational databases. In: DEXA, vol 1873 of lecture notes in computer science. Springer, pp 386–396
18.
OpenGis (1999) Opengis simple features specification for sql. Technical report Open GIS Consortium
19.
Randell DA, Cui Z, Cohn AG (1992) A spatial logic based on regions and connection. In: KR, pp 165–176
20.
Ray S, Simion B, Brown AD (2011) Jackpine: a benchmark to evaluate spatial database performance. In: Proceedings of the 27th international conference on data engineering. ICDE 2011, April 11-16, 2011, Hannover, Germany, pp 1139–1150
21.
Stock O (1997) Spatial and temporal reasoning. Kluwer Acaddemic Publishers
22.
Worboys M (1992) A geometric model for planar geographical objects. Int J Geogr Inf Syst 6(5):353–372CrossRef
Metadata
Title
Query rewriting for semantic query optimization in spatial databases
Authors
Eduardo Mella
M. Andrea Rodríguez
Loreto Bravo
Diego Gatica
Publication date
04-01-2019
Publisher
Springer US
Published in
GeoInformatica / Issue 1/2019
Print ISSN: 1384-6175
Electronic ISSN: 1573-7624
DOI
https://doi.org/10.1007/s10707-018-00335-w