Abstract | Baze podataka pokretnih objekata zasnovane su na ranijim prostorno-vremenskim bazama podataka, ali sada uključuju činjenicu da se geometrije mogu mijenjati kontinuirano, a ne samo u diskretnim trenucima. Razvijeni su modeli podataka, pridruženi su algebra i upitni jezici koji omogućuju pohranu cijele povijesti kretanja, kao i kontinuirano održavanje informacija o trenutačnoj poziciji pokretnih objekata. Te baze podataka opterećene su učestalim ažuriranjima pozicije pokretnih objekata, zbog čega se uvodi novi pristup kojim se trajektorije pokretnih objekata promatraju kao kontinuirani tokovi podataka koji sadrže informaciju o poziciji objekta u bilo kojem trenutku. U tu svrhu razvijeni su sustavi za upravljanje tokovima podataka (SUTP), koji podržavaju upravljanje kako tokovima podataka, tako i standardnim relacijama, no još uvijek imaju izrazito ograničenu podršku za prostorno-vremenske tipove podataka i operacije koje bi omogućile efikasno upravljanje pokretnim objektima. Većina dosad objavljenih istraživanja fokusirana je na baze podataka pokretnih objekata ili pak na tokove podataka, dok ih samo nekoliko nastoji kombinirati ova dva područja. Cilj istraživanja u okviru doktorske disertacije bio je proučiti aktualna istraživanja u domenama pokretnih objekata i tokova podataka proširenih generičkim prostorno-vremenskim tipovima podataka te ispitati mogućnost kombiniranja modela podataka i pridružene algebre razvijene za tradicionalne prostorno-vremenske sustave za upravljanje bazama podataka (SUBP) sa prostorno-vremenskim tokovima podataka kako bi se moglo djelotvorno upravljati pokretnim objektima. Na osnovi toga, uporabom algebre više sorti formalno je specificiran skup operacija za djelotvorno upravljanje pokretnim objektima u prostorno-vremenskim tokovima podataka te su specificirani apstraktni algoritmi za implementaciju predloženih operacija. Verifikacija rezultata istraživanja izvršena je implementiranjem predloženog modela i apstraktnih algoritama proširenjem raspoloživoga znanstveno-istraživačkog prototipa SUTP utemeljenog na relacijskom te ugradnjom definiranog skupa operacija u SQL upitni jezik s ciljem postavljanja efikasnih upita nad pokretnim objektima. Rezultat verifikacije istraživanja jest prototip sustava za djelotvorno upravljanje pokretnim objektima u prostorno-vremenskim tokovima podataka. |
Abstract (english) | Spatio-temporal database manages spatio-temporal objects and supports corresponding query languages. Term moving objects databases is today used as a synonym for spatio-temporal databases managing spatial objects with continuously changing location and/or geometry and they represent relatively intense research area in recent years. Data models and associated algebra and query languages have been developed that enable whole history of movements to be stored, as well as maintaining continuously information about the current position of moving objects. These databases are overloaded with frequent updates of moving objects positions, and new approach of considering trajectory of moving object as a continuous data stream which carries information about object position at any instant has been proposed. To manage this data, several data stream management systems (DSMS) have been developed, that support the management of data streams and standard relations as well. Mainly based on relational paradigm, they have very rudimentary support for spatiotemporal data types and operations that would enabled efficient management of moving objects. The majority of published research has focused on moving objects databases or data streams, while only a few attempts to combine these two areas. The goal of a research done within doctoral thesis was to study the current research in the field of moving objects and data streams expanded with generic spatiotemporal data types and to examine the possibility of combining data model and associated algebra developed for traditional spatio-temporal database management systems (DBMS) with spatio-temporal data streams in order to efficiently manage moving objects. Formal specification of operations for moving objects in the context of data streams is presented in this doctoral thesis by using a conceptual framework of many sorted algebra consisting of data types and operations needed to support spatiotemporal data in data streams. Abstract algorithms for the implementation of proposed operations are presented as well. An efficient implementation of suggested set of operations for managing moving objects is also analized and explored, and illustrated their embedding into SQL query language. Verification of a research has resulted in a system prototype for efficient management of moving objects in spatio-temporal data streams. The doctoral thesis is structured into eight main chapters, conclusion and appendices that are relevant for the research done within doctoral thesis. Since the spatio-temporal databases, data streams and continuous queries are the primary areas related to the moving objects management, their brief description is given in the introduction. The second chapter gives an overview of the researches relevant to the subject of doctoral thesis, which are usually performed in two separate areas of moving objects databases and data sterams. At the end of this chapter is put emphasis on a few related researches which attempt to combine moving objects with data streams. Continuous queries are one of the DSMS’s main features and are therefore considered in detail in third chapter. Main differences between one-time and continous queries and three groups of operators that may be used in continous queries are presented as well. In the area of moving objects databases, different authors presented several approaches to modeling history of movement of moving objects. Research done within doctoral thesis is based on one of those approaches and it is presented in fourth chapter in detail. This research presents data type system which enables representation of moving objects in a form of so-called “sliced representation” that is used in an approach for moving objects management in spatio-temporal data stream systems proposed in this doctoral thesis, also presented in this chapter. This approach to the modeling of moving objects in database systems can be upgraded to be applicable in spatio-temporal data stream systems as well. Data type system that represents the formal basis for modeling moving objects in data streams is also presented in this chapter. To manage moving objects in data streams efficiently, you must first extract moving object out of spatio-temporal data stream. As a part of a research done within doctoral thesis is proposed an approach for extracting moving objects out of data stream based on user defined aggregate function. This approach is described in detail in fifth chapter. Abstract algorithm for the proposed aggregate function is also specified in this chapter. Then, a formal specification for operations that will enable efficient moving objects management in spatio-temporal data stream systems is given. Since the operations for moving objects management in database area are classified in four groups, the same classification is retained in this case. Abstract algorithms for each of the operations specified in the previous section are presented in the sixth chapter. They are also classified into four groups, in accordance with classification for operations done previously. Implementation of those algorithms in an appropriate programming language enables the upgrade of existing DSMS with the proposed set of operations on moving objects. Because of its expandability feature with user-defined data types, functions and aggregate functions, TelegraphCQ prototype of DSMS developed at UC Berkeley is selected for the upgrade to the spatio-temporal data stream system prototype that will enable moving objects management. These expandability features, together with the method for creating user-defined wrappers, are discussed in the seventh chapter in detail. How the continous queries can be used in TelegraphCQ is also presented in this chapter. Implementation of a spatio-temporal data stream system prototype for the purpose of validity of the proposed approach for the moving objects management is presented in eigth chapter. Implementation of data structures for data types from type system presented in third chapter is presented first, and then the implementation of an aggregate function for extracting moving objects out of spatio-temporal data stream and implementation of functions for the proposed set of operations on moving objects. Their embedding into the SQL query language was done next, and it enables posing efficient continuous queries over moving objects in spatio-temporal data streams. Some of the most common continous queries over moving objects and their results are also presented in this chapter by using INFATI data set. The summary of this doctoral thesis and future work are given in conclusion. Since they are very closely related and used in a research done within a doctoral thesis, PostgreSQL system architecture, TelegraphCQ system architecture, PostGIS and INFATI data set are briefly presented in the form of appendix. |