Abstract
In this paper, we present a spatial logic which can be used to reason about topological and spatial relationships among objects in spatial databases. The main advantages of such a formalism are its rigorousness, clear semantics and sound inference mechanism. We also show how the formalism can be extended to include orientation and metrical information. Comparisons with other formalisms are discussed.
This work has been partially funded by the SERC under grant no. GR/G36852
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
H. Aït-Kaci, et al: “Efficient Implementation of Lattice Operations,” ACM Trans. on Programming Languages and Systems, 11(1), 1989
J. F. Allen: “Maintaining Knowledge about Temporal Intervals,” Comm. ACM26(11), 1983.
M. Aurnague: “Contribution a l'etude de la semantique formelle de l'espace et du raisonnement spatial: la localisation interne en francais, semantique et structures inferentielles”, PhD thesis, l'Universite Paul Sabatier de Toulouse, 1991.
Van Benthem: The Logic of Time, Synthese Library vol 156, Reidel, London, 1982
B. L. Clarke: “A Calculus of Individuals Based on Connection,” Notre Dame Journal of Formal LOGIC., vol. 2, No. 3, 1981.
B. L. Clarke: “Individuals and Points”, Notre Dame Journal of Formal Logic Vol. 26, No. 1, 1985.
A. G. Cohn: “A More Expressive Formulation of Many Sorted Logic,” J. Autom. Reasoning., Vol. 3(2), pp. 113–200, 1987
A. G. Cohn, D. A. Randell and Z. Cui: “A Taxonomy of Logically Defined Qualitative Spatial Relations,” Proc International Workshop on Formal Ontology in Conceptual Analysis and Knowledge Representation, Padova, Ladseb-CNR Internal Report 01/93, ed N Guarino and R Poli, pp 149–158, 1993
Z. Cui, A. G. Cohn and D. A. Randell: “ Qualitative Simulation Based On A Logical Formalism Of Space And Time”, Proc AAAI, 1992a.
Z. Cui, A. G. Cohn and D. A. Randell: “Qualitative Simulation Based On A Logic Of Space And Time”, Proc. of QR92, 1992b.
M. Egenhofer: “A Formal Definition of Binary Topological Relationships,” In: W. Litwin and H. J. Schek, editors, Third International Conference on Foundations of Data Organization and Algorithms, Paris, France, Lecture Notes in Computer Science, Vol. 367, pages 457–472, Springer-Verlag, New York, NY, June 1989
M. Egenhofer:“Reasoning about Binary Topological Relations,” In: Proceedings of the Second Symposium on Large Spatial Databases, SSD'91 (Zurich, Switzerland, 1991), O. Gunther and H. J. Schek, Eds. Lecture Notes in Computer Science 525, pp 143–160.
M. Egenhofer and J. A. Herring: “A Mathematical Framework for the Definition of Topological Relationships,” In: Proceedings of Fourth International Symposium on Spatial Data Handling (Zurich, Switzerland, 1990), K. Brassel and H. Kishimoto, Eds.
M. Egenhofer and A. Frank: “Towards a Spatial Query Language: user interface considerations,” In: Proceedings of 14th International Conference on Very Large Data Bases (Los Angeles, CA, 1988) D. DeWitt and F. Bancilhon, Eds.
M. Egenhofer and K K Al-Taha: “Reasoning about Gradual Changes of Topological Relationships”, in Theoreies and Methods of Spatio Temporal Reasoning in Geographic Space, LNCS 639 Springer Verlag, 1992
K. D. Forbus, P. Nielsen and B. Faltings: “Qualitative spatial reasoning: the CLOCK project,” Art. Int. 51, pp. 417–471, Elsevier, 1991
C. Freksa: “Using Orientation Information for Qualitative Spatial Reasoning”, Berick Nr 11, Kognitionswissenschaft, Univ. Hamburg, 1992a.
C. Freksa: “Temporal Reasoning based on Semi-intervals,” Artificial Intelligence, 54, Elsevier, 1992b
A. M. Frisch and A. G. Cohn: “Thought and Afterthoughts on the 1988 Workshop on Principles of Hybrid Reasoning,” AI Magazine 1990
A Galton, Towards an integrated logic of space, time, and motion, to appear in Proc IJCAI93, Morgan Kaufmann, 1993.
D. Guenther and A. Buchmann: “Research Issues in Spatial Databases,” SIGMOD RECORD 19 (4), 1990
R. Güting: “Geo-Relational Algebra: A Model and Query Language for Geometric Database Systems,” Advances in Database Technology, 1988.
D. Hernandez: “Using Comparative Relations to represent Spatial Knowledge”, Workshop RAUM, Univ. of Koblenz, 1990.
D. Hernandez: “Qualitative Representation of Spatial Knowledge”, PhD Dissertation, Fakultaet fuer Informatik, Technischen Universitaet Muenchen, Germann, 1992.
L. Joskowicz: “Commonsense Reasoning about Moving Objects: an Elusive Goal”, IBM T J Watson Research Center, Yorktown Heights, 1992.
B. Kuipers: “Qualitative Simulation,” Artificial Intelligence 29: 298–338, 1986
T. de Laguna: “Point, Line and Surface as sets of Solids” The Journal of Philosophy., Vol 19., pp. 449–461, 1922.
A. Mukerjee and G. Joe: “A Qualitative Model for Space”, Proc AAAI, 1990.
D. Pullar and M. Egenhofer: “Towards Formal Definitions of Topological Relations among Spatial Objects,” In: proceedings of Third International Symposium on Spatial Data Handling (Sydney, Australia, 1988), D. Marble, Ed.
D. Randell, A. G. Cohn and Z. Cui: “Naive Topology: modeling the force pump,” in Recent Advances in Qualitative Reasoning, ed B Faltings and P Struss, MIT Press, in press, 1992a.
D. A. Randell: “Analysing the Familiar: Reasoning about space and time in the everyday world,” PhD Thesis, Univ. of Warwick, UK 1991.
D. A. Randell, A. G. Cohn and Z. Cui: “Computing Transitivity Tables: a Challenge for Automated Theorem Provers,” Proc CADE11, 1992b.
D. Randell and A. G. Cohn: “Modelling Topological and Metrical Properties in Physical Processes,” in Principles of Knowledge Representation and Reasoning, ed. R. J. Brachman, H. Levesque and R. Reiter, Morgan Kaufmann, Los Altos. 1989.
D. A. Randell and A. G. Cohn: “Exploiting Lattice in a Theory of Space and Time,” Computers and Mathematics with Applications, 1992.
D. A. Randell, Z. Cui and A. G. Cohn: “A Spatial Logic based on Regions and Connection”, Proc 3rd Int Conf on the Principles of Knowledge Representation and Reasoning, Morgan Kaufmann, 1992a.
D. Randell, Z. Cui and A. G. Cohn: “An Interval Logic for Space based on “Connection”,” in proc. of ECAI92, 1992b
C. J. Rawlings, W. R. Taylor, J. Nyakairu, J. Fox and M. J. E. Sternberg: “Reasoning about Protein Topology using the Logic Programming Language PROLOG,” J. Mol. Graphics 3(4), 1985
N. Roussopoulos, C. Faloutsos and T. Sellis: “An Efficient Pictorial Database System for PSQL,” IEEE Transactions on Software Engineering 15 (5), 1988
M. Stickel: “Automated Deduction by Theory Resolution,” J. Automated Reasoning, 1, 1985
A. Tarski: “Foundations of the geometry of solids,” in Logic, Semantics, Metamathematics, trans. J. H. Woodger, Oxford Uni. Press, 1956
L. Vieu: “Semantique des relations spatials et inference spatio-temporelles: Une contribution a l'etude des structures formelles de l'espace en Language Naturel.”, PhD thesis, l'Universite Paul Sabatier de Toulouse, 1991.
A. N. Whitehead: “Process and Reality: Corrected Edition,” eds. D.R. Griffin and D.W. Sherburne, The Free Press, Macmillan Pub. Co., New York, 1978
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1993 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Cui, Z., Cohn, A.G., Randell, D.A. (1993). Qualitative and topological relationships in spatial databases. In: Abel, D., Chin Ooi, B. (eds) Advances in Spatial Databases. SSD 1993. Lecture Notes in Computer Science, vol 692. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-56869-7_17
Download citation
DOI: https://doi.org/10.1007/3-540-56869-7_17
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-56869-8
Online ISBN: 978-3-540-47765-5
eBook Packages: Springer Book Archive