Real Time Spatio-Temporal Databases

Transactions in GIS, 2001, 5(2): 87±97

Guest Editorial Real Time Spatio-Temporal Databases 1 Introduction Facing new GIS applications for which response time is a very important factor, it is necessary to envisage the creation of real time databases. By real time database, we mean that any arriving piece of information must be stored immediately, in order to be used as soon as possible, and to follow hard temporal constraints. Sometimes one is speaking about mission- or time-critical applications. This editorial describes some potential applications of real time spatio-temporal databases, introduces the reader to the principal characteristics of such new systems, and concludes by identifying a short research agenda for the immediate future.

2 Potential Applications of Real Time Spatio-temporal Databases There are many emerging new GIS applications for which time is a critical factor. For instance during disaster management, information must be collected in real time, and made immediately available to multiple potential users. In this kind of application, the characteristics of the database contents are far from the conventional view (for instance, administrative boundaries), in which the information about features changes slowly or never at all. In other words, in the past, we were dealing with applications for which the date of storing or updating information was not a very critical factor. River and flood monitoring provides another example. Numerous sensors could be distributed along the river, regularly measuring several chemical, physical, and/or biological parameters in addition to water height in this instance. After having made the measurements, the sensors send the corresponding data to a control center, for instance by using some kind of telecommunication system (could be satellite-based or use cellular phones attached to the sensors). In the control center, a front-end system manages the dialog with the sensors and stores the information into a database. Then, another system visualizes this information to give the decision-maker relevant information about the river. In addition, we can imagine boats navigating the river that are equipped for measuring some other parameters, perhaps located by GPS. When the river is very gentle, time is not a crucial factor, but when a pollution or flood event arrives, then, time becomes the more important parameter. The periodicity of collecting information must be increased, for instance passing from every hour to every minute in some instances as well. Doing so, we are multiplying the number of data to ß 2001 Blackwell Publishers, 108 Cowley Road, Oxford OX4 1JF, UK and 350 Main Street, Malden, MA 02148, USA.

88

R Laurini

be transferred, so increasing the importance of time: now all transactions must be committed very rapidly, and no system crashes will be permitted. The above-mentioned examples are but two of the many potential applications of real time spatio-temporal databases management systems (RTSTDBMS). These systems are also required for: • • • • • • • •

the management of any kind of fleet, taxis, ambulances, police, civil protection, firemen, delivery vehicles, trucks, boats, fishing ships, vessels, submarines, trains, buses, planes, rockets, etc., traffic control in order to know the vehicle flow, to send information to the drivers, to compute new itineraries, to visualize flows, and to conduct rescues and cleanup after road accidents, etc., environmental control, including air or water pollution, river, sea, volcano, hurricane monitoring, disaster management, especially during the preparedness phase, the disaster phase itself (for instance to organize assistance and rescue), and the recovery phase, hazardous materials transportation in order to guide the drivers during their travel to minimize risks in real time, any kind of delivery system (pizza, etc.), and all sorts of location aware services, all forms of surveillance or tracking, especially for mobile objects, animals or humans, stolen cars, etc., and car or boat races, in order to know in real time the relative positions of the competitors, etc.

All of these applications require some kind of RTSTDBMS in order to store and retrieve information very quickly. Figures 1 and 2 show the types of architectures that

Figure 1

Potential architecture for fleet management application ß Blackwell Publishers Ltd. 2001

Guest Editorial

Figure 2

89

Potential architecture for river monitoring application

might be appropriate for fleet management and real time river monitoring, respectively. The next section examines why conventional database management systems are not adequate for the above-mentioned applications and what specifications are required of any future RTSTDBMS.

3 From Spatial Database Systems to Real Time Spatio-temporal Database Systems Historically speaking, before the inception of DBMS in the late sixties (IMS, CODASYL and relational), and still nowadays, common files can be used to store information using a first-arrived first-installed procedure, especially for storing alphanumeric data. Faced with the difficulty of managing geographic information, the first proprietary spatial DBMS's were created in the late 1970s. During the 1980s, we saw two evolutions: (1) the arrival of object-oriented database systems (OODBMS), and (2) some GIS vendors decided not to continue to develop their own DBMSs and instead tried to integrate off-the-shelf DBMS in their systems using relational DBMSs first and then OODBMSs. In the early 1990s, investigations regarding temporal aspects were launched, both for conventional DBMS and spatial DBMS. In the late 1990s, some prototypes of real time DBMS were developed. Presently the situation is as follows: ß Blackwell Publishers Ltd. 2001

90

R Laurini

Figure 3 • • • • •

Evolution from conventional DBMS to RTSTDBMS

there is a convergence between relational and object-oriented DBMS (e.g. ORACLE 8) and some temporal aspects are integrated; spatial DBMS characteristics are also included in some systems by way of extensions: for example, ORACLE 8 allows the use of spatial information with very limited temporal capabilities; no fully spatio-temporal DBMS is marketed; no fully real time DBMS is marketed; there is a need to carry out research and develop RTSTDMS prototypes.

Figure 3 presents the different concepts of database systems and their links, and several key ideas are examined in more detail below. 3.1 Time in GIS The importance of temporal GIS has been recognized by several researchers. Several issues have been identified in the design, development and implementation of a temporal GIS (Langram 1993). Theoretical issues include spatio-temporal modelling, clustering of data and associated algorithms (Worboys 1994, Raza and Kainz 1999). In this context, process-oriented (Cheng and Molenaar 1998) and event-oriented (Peuquet and Duan 1995) spatio-temporal modeling have been proposed. Implementationrelated issues include architecture, systems, design and technological development. Futhermore, different modelling approaches require different types of spatio-temporal query languages as well (Snodgrass 1993). The main question is the semantics of time. What does time mean? What characteristics do we have to take into account? Is the meaning of time the same for archaeologists, geologists, historians, roboticians, and environmental planners? ß Blackwell Publishers Ltd. 2001

Guest Editorial

91

Another key idea in temporal systems is the need or desirability of distinguishing between two dates (bi-temporal databases). The first one is the precise date of the occurrence of an event (i.e. the event date or valid time) and the second is the date at which the information was entered into the database (i.e. the transaction time) (Jensen and Snodgrass 1999). By distinguishing those two different times, it is very easy to track any update, or error correction. Suppose that a wrong event-date t1 was initially entered for the death of a king, and that several years after, we discover the true date value t2: we can assert that during a certain time the ``database truth'' was considered as t1, although the ``database truth'' was later updated and considered as t2. However, when data are stored on a periodic scheme, the user does not know a priori whether the data at a certain time were stored or not, so often intermediate values must be retrieved. Some powerful mechanisms for temporal interpolation between stored values must be provided in these instances. A very interesting survey was recently published by the Chorochronos project participants drawn from ten European research laboratories (Frank et al. 1999). Under the coordination of Timos Sellis of the National Technical University of Athens, Greece (http://www.dbnet.ece.ntua.gr/~choros), the goal is to develop a spatiotemporal database system without any real time functionalities. Six tasks were identified ± ontology, structure and representation of space and time; models and languages for STDBMS; graphical user interfaces for spatiotemporal information; query processing in spatiotemporal databases; storage structures and indexing techniques; and global architecture ± to achieve this goal. 3.2 Real Time Database Systems Several researchers have recently investigated real-time database systems. To be suitable for real-time applications, such a database system must have fast and predictable transaction times. In other words, the temporal components of the database transactions must be small and bounded. This is especially true of those connected with disk inputs and outputs. The existing proposed solutions for improving the performance and predictability can be organized as follows (Lortz and Shin 2000): • • •

use of memory-based transactions (Garcia-Molina and Salem 1992), scheduling transactions according to task priorities (Ramamritham 1993), and reducing delays and uncertainties associated with concurrency control (Ulusoy and Buchman 1996).

See also Ozsoyoglu and Snodgrass (1995) for a survey of many of these same issues. 3.3 Main features of Realtime DBMS Storage must be easy and very rapid. Conventional solutions imposed that the database contents must be not only persistent, but also stored in secondary memories such as disks. As the access time to disk is more important than access to central memory (usually a factor from 1000 to 10,000), one interesting solution is to have everything transferred into main memory during processing. The procedure could be as follows. The database is stored on a disk. At the initialization, all the database contents are stored into the main memory. Then all transactions are made in central memory. ß Blackwell Publishers Ltd. 2001

92

R Laurini

Normally, a real time process does not finish, so there is no necessity to think about the end of the process. But for security reasons, the database contents must be archived regularly. Following temporal constraints is a very difficult challenge. One of the solutions is to avoid disk access during transactions, and to do them afterwards when the situation allows them. Another problem is that the database content is always increasing, although the main memory is limited. An interesting idea is to regularly flush the older data in the archive, in order that always, there is enough room for the data arriving in real time. By doing so, the concept of a real time database becomes totally included into real time systems. Another crucial aspect is quality control: it is impossible to imagine the consequences of erroneous decisions made in real time due to errors located in databases. Not only at the creation, but also during its lifecycle, a RTSP database must be free of any errors (Servigne et al. 2000). 3.4 Application Requirements Starting from the above-mentioned lists, we can say that the actual technology only offers either spatio-temporal DBMS without any real time functionalities, or real time DBMS without spatial characteristics; and in addition, those products are more frequently found in research centers as prototypes than as components off-the-shelf (COTS).

4 Some Additional Functionalities for any RTSTDBMS In order to set the specifications of a RTSTDBMS, several additional functionalities must be taken into account as discussed here. 4.1 Input: The Role of Sensors In conventional databases, the main data entry procedure is based on some kind of human-interface dialog. However, the main procedures will be based on sensors in the case of RTSTDBMSs. By sensors, we mean any kind of electronic device able to make measurements of some physical phenomena, and send this information to a control center by means of a telecommunication system. Three types of sensors can be distinguished: • • •

passive sensors that regularly send their measurements, for example every 10 seconds, programmable sensors for which the periodicity of the measurements can be modified remotely, intelligent sensors that are capable of some sort of ``intelligent'' behavior by taking local decisions, perhaps according to some predefined rules.

Whatever the type of the sensor, the data that are transmitted must be immediately taken into consideration. One crucial problem is when a crisis occurs. In this instance, the measuring periodicity is often accelerated and the quantity of data that is transmitted is increased. The consequence could be some sort of congestion in data ß Blackwell Publishers Ltd. 2001

Guest Editorial

Figure 4

93

Structure of a RTSTDBMS with regular flushing of data into archives

arrival, and the system must be able to manage this sudden increase within critical specified times (e.g. all measurements must be stored in less than 10 milliseconds following acquisition). 4.2 Storage As explained earlier, the key idea is to store most of the information into the main memory, especially more recent data, and to flush ancient data into an archive. For RTSPDBMS, this key idea must be accepted: in essence, a first computer can be in charge of the system, whereas a second computer must be in charge of flushing the database and managing the archives (Figure 4). Hence, not all data are stored. Some powerful mechanisms for interpolating data, either at temporal, spatial, or at both levels must be provided, especially for data corresponding to spatio-temporal continuous fields such as temperatures, pressures, winds, etc. See Laurini and Gordillo (2000) for more details. 4.3 Indexing Jensen and Snodgrass (1999) recently noted that ``the integration of temporal databases with spatial databases offers new challenges. As a single example, no really good index seems to exist for the trajectories of moving objects''. This observation certainly applies to mobile objects and it may be extended to any kind of real time DBMS. Two kinds of indexing must be maintained, one for data in main memory and one for data in the ß Blackwell Publishers Ltd. 2001

94

R Laurini

archive, to speed up access. The solution based on historical R-trees (Nascimento and Silva 1998) is an excellent candidate for both tasks. But eventually, some other high performance indexing structures will need to be discovered, studied, implemented and evaluated. 4.4 Output: Real Time Animated Visualization The preferred output is visualization, and especially real time visualization. Among visualization systems, animated cartography is a simple way to present the evolution of an object, or a process in a territory. Real time animated cartography in huge format real time interactive panels must be studied, especially as it relates to: (1) cognitive aspects of decision-making in real time, (2) graphic semiology for animated cartography, and (3) automatic selection of relevant data for synthesizing information for decision-makers. 4.5 Querying Extensions of SQL for real time (Prichard and Fortier 1997) have now been proposed. These extensions must be harmonized with those extensions dealing with spatiotemporal issues for both relational and object-oriented DBMSs. GuÈting et al. (2000) provide some initial ideas on languages for representing and querying moving objects. 4.6 Interpolation and Extrapolation In RTSTDBMS querying languages, automatic interpolations must be provided to retrieve not only locations between stored times, but also the values at specific locations, especially when dealing with continuous data (Laurini and Gordillo 2000). 4.7 Sensor Failures and Integrity Constraints Corrections In addition to robustness to sensor- or system-failures, spatial and temporal integrity constraints must be checked and maintained in real time. 4.8 Mobile GIS Whereas conventional GIS products are implemented on fixed machines, mobile GIS (Behr 1995) are characterized by the mobility of the machine (for mobile computing, refer to Barbara 1999) as in the case, for instance of a car, a truck or a boat. Mobile GIS can be defined as installed on an on-board machine, and sometimes the expression embarked GIS is also used. By using GPS intensively, mobile GIS offer de facto real time systems, especially when linked with some control center. See also Wolfson (1998) for a review of these issues. 4.9 Transactions Two kinds of transactions that are very different and modify the contents of the database contents should be mentioned: ß Blackwell Publishers Ltd. 2001

Guest Editorial • •

95

Short transactions for inserting data coming from sensors into the database. These have a very high level of priority, similar to other kinds of short transactions. Long transactions for flushing the old data of the main database into archive(s). These have a very low level of priority unless the main database is nearly fully populated.

Any new RTSTDBMS must take these characteristics into account. 4.10 Disk Management and Archives As explained earlier, we need a structure in which there is a main disk, and some archives. When necessary, some extra archive disks must be added without stopping the system. 4.11 Interoperability Although interoperability is not the goal of any RTSTDBMS, this requirement is nagging for users. A solution is that the data model must be compliant with standards such as those proposed by the OpenGIS Consortium (Buelher and McKee 1996). Spatial models were tackled first, and attention has now shifted to spatio-temporal data. There is currently (as far as I know) no standards for real time spatio-temporal data. 4.12 Links to the Internet Internet links must be provided and a URL must be considered as an abstract data type in order to embed hypermap capabilities in the RTSTDBMS (Laurini and MilleretRaffort 1990). 4.13 Security and Computer Failures As with any real time system, robustness is a key issue. The RTSTDBMS must provide security for any user, especially when facing computer failures. 4.14 Conceptual Data Models For analysis and design purposes, conceptual data models must be invented that take not only spatio-temporal aspects, which is already done (e.g. Price et al. 1999) but also real time characteristics (Douglas 1998) into account. These tools will facilitate the design of new GIS applications integrating real time components.

5 Conclusions Integrating real time aspects into GIS is a new challenge for the GIS community, linked to the development of telegeoprocessing and telegeomonitoring activities (Laurini 2001, Laurini et al. 2001). Real time spatio-temporal database systems are needed to accomplish this integration. Research must be conducted on the following topics: ß Blackwell Publishers Ltd. 2001

96

R Laurini

conceptual modeling, database architectures, storage and indexing, management of spatio-temporal integrity constraints, mobile GIS, languages, and cognitive aspects to build these systems. My vision is, by designing new applications, the system developers will face new problems, and so create new concepts. Robert Laurini LISI ± INSA Claude Bernard University of Lyon

References Barbara D 1999 Mobile computing and databases: A survey. IEEE Transactions on Knowledge and Data Engineering 11: 108±17 Behr F J 1995 Mobile GIS: Contributing To Corporate Benefits. WWW document, http:// www.graphservice.de/papers/mobile_g.htm Buelher K and McKee L (eds) 1996 The OpenGIS Guide: An Introduction to Interoperable Geoprocessing. Wayland, MA, OpenGIS Consortium Cheng T and Molenaar M 1998 A Process-oriented Spatio-temporal Data Model to Support Physical Environmental Modeling. In Proceedings of the Eighth International Conference on Spatial Data Handling, Vancouver, Canada: 418±30 Douglas B P 1998 Real-time UML: Developing Efficient Objects for Embedded Systems. New York, Addison Wesley Frank A, Grumbach S, GuÈting R H, Jensen C S, Koubarakis M, Lorentzos N A, Manalopoulos Y, Nardelli E, Pernici B, Schek H -J, Scholl M, Sellis T K, Theodoulidis B, and Widmayer P 1999 Chorochronos: A research network for spatio-temporal database systems. SIGMOD Record 28: 12±21 Garcia-Molina H and Salem K 1992 Main memory database systems: An overview. IEEE Transactions on Knowledge and Data Engineering 4: 509±16 Guting R H, Bohlen M H, Erwig M, Jensen C S, Lorentzos N A, Schneider M, and Vazirgiannis M 2000 A foundation for representing and querying moving objects. ACM Transactions on Database Systems 25: 1±42 Jensen C S and Snodgrass R T 1999 Temporal data management. IEEE Transactions on Knowledge and Data Engineering 11: 6±44 Langram G 1993 Issues of implementing a spatio-temporal system. International Journal of Geographical Information Systems 7: 305±14 Laurini R 2001 Information Systems for Urban Planning: A Hypermedia Co-operative Approach. London, Taylor and Francis (forthcoming) Laurini R and Gordillo S 2000 Field orientation for continuous spatio-temporal phenomena. In Proceedings of the International Workshop on Emerging Technologies for Geo-based Applicatons, 22±26 May, Ascona, Switzerland. Lausanne, Swiss Federal Institute of Technology: 77±101 Laurini R and Milleret-Raffort F 1990 Principles of Geomatic Hypermaps. In Proceedings of the Fourth International Symposium on Spatial Data Handling, 23±27 July, Zurich, Switzerland: 642±51 Laurini R, Servigne S, and Tanzi T 2001 A Primer of TeleGeoProcessing and TeleGeoMonitoring. Computers, Environment and Urban Systems 25: in press Lortz V B, Shin K G, and Kim J 2000 MDARTS: A multiprocessor database architecture for hard real-time systems. IEEE Transactions on Knowledge and Data Engineering 12: 621±44 Nascimento M A and Silva J R O 1998 Towards Historical R-trees. In Proceedings of the ACM Symposium on Applied Computing (ACM-SAC), Atlanta: 235±40 Ozsoyoglu G and Snodgrass R T 1995 Temporal and real-time databases: A survey. IEEE Transactions on Knowledge and Data Engineering 7: 513±32 Peuquet D and Duan N 1995 An event-based spatio-temporal data model for temporal analysis of geographic data. International Journal of Geographical Information Systems 9: 7±24 ß Blackwell Publishers Ltd. 2001

Guest Editorial

97

Price R, Srinivasan B, and Ramamohanarao K 1999 Spatiotemporal Extensions to Unified Modeling Language. In Proceedings of the Tenth International Workshop on Database and Expert Systems Applications, 1-3 September, Florence, Italy: 460±1 Prichard J and Fortier P 1997 Real-Time SQL. In Proceedings of the Second International Workshop on Real-Time Databases, 18±19 September, Burlington, Vermont: 289±310 Ramamritham K 1993 Real time databases. International Journal of Distributed and Parallel Databases 1: 199±226 Raza A and Kainz W 1999 Cell Tuple-Based Spatio-temporal Data Model: An Object-oriented Approach. In Proceedings of ACM GIS'99, New York: 20±5 Servigne S, Ubeda T, Puricelli A, and Laurini R 2000 A methodology for spatial consistency improvement of geographic databases. GeoInformatica 4: 7±34 Snodgrass R T 1993 An overview of Tquel. In Tansel A, Clifford J, Gadia S, Jajodia S, Segev A, and Snodgrass R T (eds) Temporal Databases: Theory, Design and Implementation. New York, Benjamin/Cummings: 141±82 Ulusoy O and Buchmann A 1996 Exploiting main memory DBMS features to improve real-time concurrency control protocols. SIGMOD Record 25: 23±5 Wolfson O 1998 Moving Objects Databases: Issues and Solutions. In Proceedings of the Tenth International Conference on Scientific and Statistical Database Management (SSDBM98), 1± 3 July, Capri, Italy: 111±22 Worboys M 1994 A unified model of spatial and temporal information. Computer Journal 37: 26±34

ß Blackwell Publishers Ltd. 2001