Abstract
The increasing demand for the use of database systems as an integrating factor in CAD/CAM applications has necessitated the development of database systems with appropriate modelling and retrieval capabilities. One essential problem is the treatment of geometric data which has led to the development of spatial databases. Unfortunately, most proposals only deal with simple geometric objects like multidimensional points and rectangles. On the other hand, there has been a rapid development in the field of representing geometric objects with free form curves or surfaces, initiated by engineering applications such as mechanical engineering, aviation or astronautics. Therefore, we propose a concept for the realization of spatial retrieval operations on geometric objects with free form boundaries, such as B-spline or Bézier curves, which can easily be integrated in a database management system. The key concept is the encapsulation of geometric operations in a so-called query processor. First, this enables the definition of an interface allowing the integration into the data model and the definition of the query language of a database system for complex objects. Second, the approach allows the use of an arbitrary representation of the geometric objects. After a short description of the query processor, we propose some representations for free form objects determined by B-spline or Bézier curves. The goal of efficient query processing in a database environment is achieved using a combination of decomposition techniques and spatial access methods. Finally, we present some experimental results indicating that the performance of decomposition techniques is clearly superior to traditional query processing strategies for geometric objects with free form boundaries.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Asano, T.; Asano, T.: Minimum Partition of Polygonal Regions into Trapezoids; Proc. 24th IEEE Annual Symposium on Foundations of Computer Science, 1983, 233–241.
Beacon, G.R.; Dodsworth, J.R.; Howe, S.E.; Oliver, R.G.; Saia, A.: Boundary Evaluation Using Inner and Outer Sets: The ISOS Method; IEEE Computer Graphics and Applications, March 1989, 39–51.
Brinkhoff, T.; Kriegel, H.-P.; Seeger, B.: Efficient Processing of Spatial Joins Using Rtrees; Proc. ACM SIGMOD Int. Conf. on Management of Data, Washington D.C., Mai 1993.
Brinkhoff, T.; Kriegel, H.-P.; Schneider, R.: Comparison of Approximations of Complex Objects Used for Approximation-based Query Processing in Spatial Database Systems; Proc. 9th Int. Conf. on Data Engineering, Vienna, Austria, 1993, 40–49.
Fahldieck, A.; Mysliwitz, N.: ‘Models for Processing Geometric Objects described by Free Form Surfaces in Database Systems'; Master Thesis, University of Bremen, January 1992 (in German).
Güting, R.H.: Gral: An Extensible Relational Database System for Geometric Applications; Proc. 15th Int. VLDB Conference, Amsterdam, 1989, 33–44.
Heep, S.: ‘Queries on Geometry Data in CAD Database Systems'; Ph.D.Thesis, University of Bremen (in German).
Hoschek, J.; Lasser, D.: ‘Basics of Geometric Data Processing'; Teubner 1989 (in German).
Katz, R.: Information Management for Engineering Design; Springer, Berlin Heidelberg, 1985.
Keil, J.M.; Sack, J.R.: Minimum Decompositions of Polygonal Objects; in: Toussaint, G.T. (ed.): Computational Geometry; Elsevier Science Publishers B.V. (North Holland), 1985, 197–216.
Kriegel, H.-P; Heep, P.; Heep, S.; Schiwietz, M.; Schneider, R.: An Access Method Based Query Processor for Spatial Database Systems; Proc. Int. Workshop on DBMS for Geographical Applications, Capri, May 16–17, 1991; in: Geoegraphic Database Management Systems, Springer, 1992, 272–292.
Kriegel, H.P.; Schiwietz, M.; Schneider, R.; Seeger, B.: Performance Comparison of Point and Spatial Access Methods; Proc. Symposium on the Design and Implementation of Large Spatial Databases, Santa Barbara, USA, July 1989, 89–114.
Kriegel, H.-P; Horn, H.; Schiwietz, M.: The Performance of Object Decomposition Techniques for Spatial Query Processing; Proc. 2nd SSD'91, Zürich, August 1991; in: Günther, O.; Schek, H.-J. (eds): Advances in Spatial Databases; published as LNCS 525, Springer, 257–276.
Orenstein, J.A.; Manola, F.A.: Spatial Data Modeling and Query Processing in PROBE; Technical Report CCA-86-05, Computer Corporation of America, Four Cambridge Center, Cambridge, MA, October 1986.
Samet, H.: The Design and Analysis of Spatial Data Structures; Addison-Wesley, Reading, MA, 1990.
Schneider R., Kriegel H.P., Seeger B., Heep S.: Geometry-based Similarity Retrieval of Rotational Parts; Proc. Int. Conf. on Data and Knowledge Systems for Manufacturing and Engineering, Gaithersburg, Maryland, 1989, 150–160.
Widmayer, P.: Data Structures for Spatial Databases; in: Vossen, G.; Witt, K.-U. (eds.): ‘Future Trends in Database Systems', Oldenbourg, 1991 (in German).
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1993 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Kriegel, HP., Heep, S., Fahldiek, A., Mysliwitz, N. (1993). Query processing of geometric objects with free form boundaries in spatial databases. In: Mařík, V., Lažanský, J., Wagner, R.R. (eds) Database and Expert Systems Applications. DEXA 1993. Lecture Notes in Computer Science, vol 720. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-57234-1_31
Download citation
DOI: https://doi.org/10.1007/3-540-57234-1_31
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-57234-3
Online ISBN: 978-3-540-47982-6
eBook Packages: Springer Book Archive