Transcript A Multi-Tier Spatio

Ontology for Moving
Points/Objects/Change...
What can ontology contribute to our
debate?
Andrew U. Frank
Geoinformation
TU Vienna
[email protected]
www.geoinfo.tuwien.ac.at
From Moving Points to Moving Objects –
an ontological contribution in 3 pieces:
1. andante:
What should an ontology for moving objects
contain?
2. largo:
How to formalize an ontology for moving objects?
3. vivace:
What can we achieve with it?
Andew U. Frank
4. Nov. 2008
Ontology today
Ontology in information science is defined as
“an explicit formal specification of the terms
in the domain and relations among them”.
Andew U. Frank
4. Nov. 2008
Ontology captures structure
Structure of the data is represented in
• is_a relations
• part_of relations
• Instance relations
Andew U. Frank
4. Nov. 2008
Two critical observations:
1. a static view: no process, no operations,
nothing changes;
2. it is very difficult:
imagine how difficult it is
to describe the structure
of a dish (e.g. apple pie)
in contrast to the recipe
(a description of a process)
Andew U. Frank
4. Nov. 2008
Discussing ontology means first
discussing the formal methods to
describe ontologies:
Natural language descriptions of ontologies are
not clarifying the semantics an ontology
purports to clarify.
Andew U. Frank
4. Nov. 2008
Formal methods to describe ontologies
(highly simplified):
1. Construct a particular formal language for the
type of ontology you are interested in:
- ontology for GIS
- ontology for moving objects
- ontology for flocks ...
Andew U. Frank
4. Nov. 2008
Ontology languages 1: UML
Informal, but extensive use:
Uniform Modeling Language (UML) – limited by
lack of formal definition – no conclusions drawn or
consistency checked automatically.
Tools (graphical editors) for UML are available:
Nice, easy to use, flexible – but no formal
background, therefore no fixed semantics, not
much can be checked for consistency!
Andew U. Frank
4. Nov. 2008
Ontology languages 2: Description logics
consists of
• A set of unitary predicates denote concept
names
• A set of binary relations, which denote role
names
• Recursive constructors to form more complex
constructs from the concepts and roles.
Andew U. Frank
4. Nov. 2008
Many variants of Description Logics:
Various DL with different levels of expressive
power and computational complexity,
depending which constructors are included:
– union and intersections of concepts
–negation of concepts
– value (universal) restriction
– existential restriction
Andew U. Frank
4. Nov. 2008
Actual languages:
The Web Ontology Language OWL (the
culmination from a sequence of KL-ONE
(1985).... DAML, OIL, DAML+OIL).
A compromise between expressive power and
tractability of logical deductions (goal:
consistent theory!)
Practically: very limited and difficult to use.
Andew U. Frank
4. Nov. 2008
Example “Person - Gender”:
<rdf:RDF
xmlns:rdf="http://www.w3.org/1999/02/22-rdf-syntax-ns#"
xmlns:rdfs="http://www.w3.org/2000/01/rdf-schema#"
xmlns:owl="http://www.w3.org/2002/07/owl#"
xmlns="http://localhost:8080/OWLBuergerInformation.owl#"
xml:base="http://localhost:8080/OWLBuergerInformation.owl">
<owl:Ontology rdf:about=""/>
<owl:Class rdf:ID="Gender"/>
<owl:Class rdf:ID="Person"/>
<owl:Class rdf:ID="Woman">
<rdfs:subClassOf rdf:resource="#Person"/>
<owl:equivalentClass>
<owl:Restriction>
Andew U.
Frank
4. Nov. 2008
<owl:onProperty
rdf:resource="#Gender"/>
<owl:hasValue rdf:resource="#female" rdf:type="#Gender"/>
Ontology editors, e.g. Protege
Ontology editor based on description logic.
Produces ontologies in different output
languages (e.g. OWL-Light).
Very difficult to use, very time consuming.
Andew U. Frank
4. Nov. 2008
Example: definition of pizza
Gives list of incredients (structure) but not the
process of baking one!
Andew U. Frank
4. Nov. 2008
Extend ontology descriptions with time,
change, process
Why is this difficult?
1. First order logic is essentially static, adding
time
- adds confusing bulk to expression:
move (P, A, B, T) :is_at (P, A, T1) & is_at (P, B, T2) & before (T1, T)
& after (T2, T)
- frame problem:
need to state what does not change to allow logical
inference
Andew U. Frank
4. Nov. 2008
First order logic:
Difficult to represent change and process in first
order logic
(complicated temporal logics would be needed)
Andew U. Frank
4. Nov. 2008
Using existing languages for ontology
modelling:
Algebraic background, to be prepared to describe
operations and change.
Mathematical rigor and simplicity:
functional languages.
Andew U. Frank
4. Nov. 2008
Example:
Specification of classes
“Boat House” and “Houseboat”.
(Kuhn:Cosit'06) in Haskell (www.haskell.com)
Gives:
classes and subclasses
operations for objects of these classes
Semantics is defined by operations!
Andew U. Frank
4. Nov. 2008
Ontologies with operations is an objectoriented ontology!
In an object orientation view the world consists
of
objects with operations!
The object-oriented research in software
engineering concentrates uses an algebraic
approach to model object classes and
operations applicable to the objects.
Andew U. Frank
4. Nov. 2008
Formalization Subclass:
Dogs are Animals; they breath and bark:
class Animals a where
breath :: a -> StateChange World
class Animals => Dogs d where
bark :: d -> StateChange World
eat :: d -> f -> StateChange World
Andew U. Frank
4. Nov. 2008
Programming with inheritance:
The is_a relation does not translate directly to the
operations.
class Numbers n where
division :: n -> n -> n
instance Numbers Rational
instance Numbers Int
Int is subset of Rational
Andew U. Frank
4. Nov. 2008
2nd Problem: Contravariance of Functions
functions are contra-variant:
applying a function to subsets of the arguments does not guarantee
that the result will be a subset of the result of the original
function.
Andew U. Frank
4. Nov. 2008
Solution
Parametric polymorphism, as shown in the
above example, where
class Numbers n where ...
has a parameter n.
The usual ad-hoc polymorphism of current
programming languages (C++, Java) is not
theoretically clean.
Andew U. Frank
4. Nov. 2008
Formalizing 1: Moving point
a moving point is a list of tuples (fixes)
t, x, y (,z)
this is what most understand by trajectory,
interpreting that the same point was observed
at the given location at the given time.
Andew U. Frank
4. Nov. 2008
Formalizing 2: Moving point as a
function
a moving point is a function
p (t) = ...
e.g.
p (t) = (x0 + vx * t, y0 + vy * t)
but using a lookup function in the list of fixes
and interpolating between known locations
can be written as a function as easily.
Andew U. Frank
4. Nov. 2008
Formalizing 3: Moving and changing
objects
an object can not only change position, but any
other property (heading, speed, color,
ownership...)
Model each property as a function from time and
objectID to value
e.g. speed (ID, t) = v
color (ID, t) = c
Andew U. Frank
4. Nov. 2008
Formalizing 4: Many changing objects in
a world
Populate a world with many objects which
change (e.g. SWARM). How to check for
interaction between objects, expressed
formally!
(Model objects as autonomous agents, with
capabilities to obseve the world...)
Andew U. Frank
4. Nov. 2008
Formalizing 5: Operations of objects
produce change in the state of the world:
operations for objects start with a state of the
world and result in a changed new world
state:
op:: ID -> WorldState -> WorldState
w1 := op (id, w0)
Andew U. Frank
4. Nov. 2008
Formalizing with Monads:
op :: ID -> ChangeWorldState
(where ChangeWorldState = WorldState ->
WorldState)
The result of applying an operation to an object
(and possible additional parameters) is a
function, chaning the world from current state
to a next state.
Andew U. Frank
4. Nov. 2008
Special Monad, so called State Monad:
nice algebraic properties for the monad
opereations “return” and “binb”:
"return" must preserve all information about its
argument.
(return x) >>= f ≡ f x
m >>= return ≡ m
Andew U. Frank
4. Nov. 2008
Special Monad, so called State Monad:
Binding two functions in succession is the same
as binding one function that can be
determined from them.
(m >>= f) >>= g
≡ m >>= (\x -> f x >>= g)
Andew U. Frank
4. Nov. 2008
Special Monad, so called State Monad:
A monad can define a "zero" value for every
type. Binding a zero with any function
produces the zero for the result type, just as 0
multiplied by any number is 0.
mzero >>= f ≡ mzero
Similarly, binding any m with a function that
always returns a zero results in a zero
m >>= (\x -> mzero) ≡ mzero
Andew U. Frank
4. Nov. 2008
Paradigm change necessary:
Two traditions that are hindering temporal GIS
and the necessary ontologies with processes:
- logic (especially Description Logics)
- Inheritance in (imperativ) programming
languages (especially C++ and Java)
Andew U. Frank
4. Nov. 2008
Ontology description with algebra :
operations are explicit changing state to new
state
t1 = f (t0)
class hierarchy with parametrised
polymorphism.
Tools: functional programming languages (eg.
Haskell, Caml, Scheme, ML)
Andew U. Frank
4. Nov. 2008
Paradigm change must fix
more than one problem!
I have argued for a paradigm
change in the methods to
describe ontologies.
Does this address other pressing
problems?
Andew U. Frank
4. Nov. 2008
An ontology based on operations could
be used to more than just “clarify
semantics”:
The ontology gives a theory!
Constructing a model checks that the model
corresponds to our intuition.
Formal ontologies should allow entering
instances and observe their behaviour (e.g.
Protege)
Andew U. Frank
4. Nov. 2008
How?
The data structure part (static ontology) can be
used to present the data – this is standard for
administrative data processing.
The operations described in the ontology give a
computational model.
Andew U. Frank
4. Nov. 2008
Ontology with operations
equals “prototype application”
Test the ontology! Improve code where not
appropriate.
Ontology gives automatically (minimal, but
standardized) interface.
Slogan:
GUI's from ontology for free!
Andew U. Frank
4. Nov. 2008
How? Translate the operations to buttons and
Finale
It is necessary and worthwhile to jump to a new
paradigm and build ontologies with
operations!
Andew U. Frank
4. Nov. 2008