Transcript Un Lenguaje de Consulta Orientado a Eventos y sus Relaciones

A Graph-Oriented Model and
Query Language for Events
Miguel Romero
University of Bío-Bío, Chile
[email protected]
Andrea Rodríguez
University of Concepción, Chile
[email protected]
Contents
► Introduction
► Events
► Query
Model
Language
► Prototype
► Conclusions
november 8,
2007
and future work
Miguel Romero and Andrea Rodríguez. SeCoGis'07 at Auckland, New Zealand,
2
Introduction
►
Events are present in diverse areas as: simulation, active
database, business process and so on
►
Two complementary views of events in information
systems are.
 events are triggering conditions rather than being stored and
queried as traditional data, such as events in active databases and
in reactive Web applications and services.
 events are subject of data representation and query processing,
such as events in spatio-temporal databases.
november 8,
2007
Miguel Romero and Andrea Rodríguez. SeCoGis'07 at Auckland, New Zealand,
3
Introduction
►
We consider events in the context of spatio-temporal
databases, where events establish something that happens
at a specific location and time instant or interval.
►
Considering events as subject of representation leads us to
model events as entities in a database system.
►
Unlike entities in traditional databases systems,
relationships between events, play an important role for
querying events, like temporal order, spatial connectivity or
causality.
november 8,
2007
Miguel Romero and Andrea Rodríguez. SeCoGis'07 at Auckland, New Zealand,
4
1960 Chilean Earthquake
6
Tsunami (type)
Hawai (place)
23/05/60 07:00 (date-time)
10m (wave height)
Earthquake (type) 1
Concepción (epicenter)
21/05/60 6:33 (date-time)
7.25 (strength)
2
Earthquake (type)
Concepción (epicenter)
22/05/60 14:58 (date-time)
7.5 (strength)
8
Volcano eruption (type)
Puyehue volcano (place)
23/05/60 (day)
Earthquake (type)
Valdivia (epicenter)
22/05/60 15:40 (date-time)
9.5 (strength)
3
5
Tsunami (type)
Valdivia (place)
22/05/60 16:20 (date-time)
10m (wave height)
9
Landslides (type)
Tralcan mountain (place)
22/05/60 15:40(date-time)
Flood (type)
Valdivia (place)
22/05/60 – 26/05/60
(interval)
4
Outflow block (type)
Riñihue lake (place)
22/05/60 – 23/05/60
(interval)
november 8,
2007
7
Miguel Romero and Andrea Rodríguez. SeCoGis'07 at Auckland, New Zealand,
5
Introduction
The main contribution of the work is to
address modelling, representation, and
query specification of events from a
different perspective, where the focus is to
query about events rather than about the
changes in objects’ states.
november 8,
2007
Miguel Romero and Andrea Rodríguez. SeCoGis'07 at Auckland, New Zealand,
6
Events Model
►
In this work, we extend models and query languages for
graphs to represent events as follows:
Earthquake (type)
Valdivia (epicenter)
22/05/60 15:40 (date-time)
9.5 (strength)
Tsunami (type)
Valdivia (place)
22/05/60 16:20 (date-time)
10m (wave height)
1. Events are represented as nodes in a graph, with their
particular properties (temporal and spatial settings).
2. Edges in a graph represent causality relationships
between events.
3. Both events and causality relationships can be
modelled at different levels of granularity.
november 8,
2007
Miguel Romero and Andrea Rodríguez. SeCoGis'07 at Auckland, New Zealand,
7
Different levels of granularity
november 8,
2007
Miguel Romero and Andrea Rodríguez. SeCoGis'07 at Auckland, New Zealand,
8
Events Model
EVENT*  EDGE*  EVENT_GRAPH event_graph
LABEL+  (ATOMIC_EVENT  COMPOSITE_EVENT)  EVENT event
ATOMIC_EVENT  EVENT_GRAPH  COMPOSITE_EVENT composite_event
INTERVAL  SPATIAL  ATOMIC_EVENT atomic_event
LABEL+  (ATOMIC_EDGE  COMPOSITE_EDGE)  EDGE edge
COMPOSITE_EVENT  COMPOSITE_EVENT  EDGE*  COMPOSITE_EDGE composite_edge
EVENT  EVENT  ATOMIC_EDGE atomic_edge
INSTANT  INSTANT  INTERVAL interval
string  BASE  LABEL label
string  INSTANT instant
* Set type
+ List type
november 8,
2007
 SPATIAL point, line, polygon, region
 BASE int, real, string, bool
Miguel Romero and Andrea Rodríguez. SeCoGis'07 at Auckland, New Zealand,
9
Main Operators
► Event_graph
 events, edges: returns a set of events or edges
 get_event, get_edge: returns a particular event or edge.
 project_each_event, project_each_edge: projection of
labels.
 select_each_event, select_each_edge: filter the graph with
a function selection.
 union, intersection, difference of graph
november 8,
2007
Miguel Romero and Andrea Rodríguez. SeCoGis'07 at Auckland, New Zealand,
10
Main Operators (cont.)
►
Event
 is_atomic: is true for atomic event
 get_graph, get_interval:, get_spatial: return a graph, interval and spatial
setting.
 str_Label_Value, int_Label_Value, real_Label_Value: return a label’s
value.
►
Edge
 is_atomic: is true for atomic edge
 edges, source, target: return a set of edges, source event and target event
 str_Label_Value, int_Label_Value, real_Label_Value: return a label’s
value.
november 8,
2007
Miguel Romero and Andrea Rodríguez. SeCoGis'07 at Auckland, New Zealand,
11
Main Operators (cont)
►
Interval:
 start, end: time point of interval
 classic Allen Operator: equals , diferent, before, after, meets, metby, finishes,
finishedby, overlaps, overlappedby, starts, startedby, during, contains;
november 8,
2007
Miguel Romero and Andrea Rodríguez. SeCoGis'07 at Auckland, New Zealand,
12
Query Language
►
All events and their relationships ocurred before of “1961/01/01” in Chile
and Argentina.
1961
earthquakeChileDB
query
earthquakeChileDB do
1
select_each_event(fun(ev: event)
earthquakeArgentinaDB
7
3
union
earthquakeArgentinaDB do
select_each_event(fun(ev: event)
get_interval(ev) before new_interval(“1961”))
Done
6
3
get_interval(ev) before new_interval(“1961”))
Done
5
2
4
8
Result of query
1
5
3
2
november 8,
2007
Miguel Romero and Andrea Rodríguez. SeCoGis'07 at Auckland, New Zealand,
4
13
Lenguaje en BNF
<query>::= query {<graph formula>|<event formula>|<edge formula>}
<graph formula> ::= {<graph query>|<graph expression>|<graph object>}
<graph query> ::=
<graph formula> do
[project_each_event(<label name>[{, <label name>}…])]
[project_each_edge(<label name>[{, <label name>}…])]
[select_each_event(fun(<var name>:event)<boolean formula>)]
[select_each_edge(fun(<var name>:edge)<boolean formula>)]
done
<graph expression> ::= { <graph formula> union <graph formula>
| <graph formula> intersection <graph formula>
| <graph formula> difference <graph formula> | get_event_graph(<event formula>) }
<path formula> ::= <path object> | paths(<graph formula>)
<event formula>::= <event object> | <event out operator>
<edge formula> ::= <edge object> | <edge out operator>
<boolean formula> ::= <boolean object> | not(<boolean formula>)
| <boolean formula> and <boolean formula>
| <boolean formula> or <boolean formula>
| < relational formula>| < allen formula>
november 8,
2007
Miguel Romero and Andrea Rodríguez. SeCoGis'07 at Auckland, New Zealand,
15
Implementation
►
SECONDO, an extensible Database Systems
 Generic database system framework,
 extended by: algebra module, viewer object and optimizer rueles.
►
we extended SECONDO by:
 New algebra module: Event Algebra (EA).
 New viewer objects : Event viewer (EV).
EV
EA
SECONDO Components
november 8,
2007
Architecture of the kernel
Miguel Romero and Andrea Rodríguez. SeCoGis'07 at Auckland, New Zealand,
16
Secondo GUI
november 8,
2007
Miguel Romero and Andrea Rodríguez. SeCoGis'07 at Auckland, New Zealand,
17
Conclusion and future works
►
we proposed a graph-based approach to modeling events and their
interrelations.
►
We discussed the need of making explicit the relationships between events,
and we have extended current graph data models to include temporal and
spatial settings and to manage different levels of granularity for representing
events and their relationships.
►
As future work, we would like to fully implement the model in the extensible
database system, by including path queries and interoperation with existing
spatial algebras. The event query language can be extended and adapted to
standard query languages.
►
There are also research issues concerning temporal granularity that could be
further addressed, as well as reasoning with unknown temporal or spatial
settings.
►
We also evaluate to use another graph oriented language (e.g. XQuery) to
implement this model.
november 8,
2007
Miguel Romero and Andrea Rodríguez. SeCoGis'07 at Auckland, New Zealand,
18
A Graph-Oriented Model and
Query Language for Events
Thanks!
Miguel Romero
University of Bío-Bío, Chile
[email protected]
Andrea Rodríguez
University of Concepción, Chile
[email protected]