Modeling and Querying History of Movement Data Structures
Modeling and Querying History of Movement Data Structures
Principles
2 true 0 2 (0;1) (2;0) 1 0 true i=0 i=1 a points value with:
number of components (points)
minimum bounding box
an array of point values Map discrete model into data structures usable to represent attribute data types in a DBMS:
A data type is a record that contain:
elements of fixed-size
references to arrays that store the sets of possibly varying size
The arrays can be possibly large arrays of widely varying size:
use tools from the DBMS implementation environment to store such arrays:
if the array is not large, store it together with the whole database object (e.g., relational tuple); otherwise store the array separately
Base Types
2 true A record of two values:
a value, v
a defined flag, d
Implementation in SECONDO:
class CcReal: public StandardAttribute
{
..........
private:
bool defined;
float realVal;
}
typedef char STRING[MAX_STRINGSIZE+1] class CcString: public StandardAttribute
{
..........
private:
bool defined;
STRING stringVal;
}
Point Type
1 0 true A record of three values:
an x-coordinate, x
a y-coordinate, y
a defined flag, d
Implementation in SECONDO:
class Point: public StandardSpatialAttribute
{
..........
protected:
bool defined;
Coord x;
Coord y;
}
Points Type
2 true 0 2 (0;1) (2;0) 1 0 true i=0 i=1 A record containing:
summary fields:
number of components
minimum bounding box
an array of point values
(ordered lexicographically)
Implementation in SECONDO:
class Points: public StandardSpatialAttribute
{
..........
private:
DBArray points;
Rectangle bbox;
}
Line Type
s1 s2 s3 s4 (s1, left) (s4, left) (s4, right) (s1, right)
(s2, left) (s2, right) (s3, left) (s3, right)
A record containing:
summary fields:
number of components
minimum bounding box
length
an array of halfsegments
Each segment s = (p1, p2) is mapped to two halfsegments:
h1 = (s, left), where p1 is dominating point
h2 = (s, right), where p2 is dominating point
Order on halfsegments:
Basically, order of traversal by plane-sweep algorithms
Formally:
if dp(h1) < dp(h2) then h1 < h2
else if dp(h1) = dp(h2) and h1 is right and h2 is left then h1 < h2
else if h1 and h2 are same and rot(h1, h2) then h1 < h2
Line Type
A record containing:
summary fields:
number of components
minimum bounding box
length
an array of halfsegments
Implementation in SECONDO:
class Line: public StandardSpatialAttribute
{
..........
private:
DBArray line;
Rectangle bbox;
int pos;
}
Region Type
s1 s2 s6 s4 s3 s5 s1, left s2, left s3, left s4, left s4, right s5, left s2, right s6, left s5, right s3, right s6, right s1, right A record containing:
summary fields:
number of components
minimum bounding box
area
perimeter
an array of halfsegment records
an array of cycle records
an array of faces records
Order on halfsegments is as with lines
Each halfsegment record has:
a halfsegment
an index of next segment in cycle
Cycle records and faces records are also linked together:
E.g., it is possible to traverse the list of cycles that belong to a face
SECONDO implementation does not have cycles array and faces array?
Comments