-----------------------------------------------------------------------------
Functional Constraints in Ontology Reasoning
-----------------------------------------------------------------------------
Andrea Cali'
University of London & Oxford University
-----------------------------------------------------------------------------
Mercoledi' 5 Dicembre 2012 - Ore 11:30 Sala Riunioni
Dip. di Informatica e Automazione - Universita' Roma Tre
Via Vasca Navale, 79 00146 Roma
-----------------------------------------------------------------------------
Sommario
When data schemata are enriched with expressive constraints that aim
at representing the domain of interest, in order to answer queries one
needs to consider the logical theory consisting of both the data and
the constraints. Query answering in the presence of constraints that
allow for the inference of new information is usually called
ontological query answering. Commonly adopted database constraints in
this field are tuple-generating dependencies (TGDs) and
equality-generating dependencies (EGDs), the latter being in fact
functional constraints. It is well known that the interaction of TGDs
and EGDs leads to intractability or undecidability of query answering
even in the case of simple subclasses. The main (semantic) condition
that guarantees a loose interaction between these two types of
constraints is called separability. Separability often guarantees
tractability, as long as the theory is satisfiable. In this talk we
review the main notions of separability found in the literature, as
well as several syntactic conditions that are sufficient to prove
them. We then shed light on the issue of satisfiability checking,
showing that under a sufficient condition called deep separability it
can be done by considering the TGDs only. We show that, fortunately,
in the case of TGDs and EGDs, separability implies deep separability.
This result generalizes several analogous ones, proved ad hoc for
particular classes of constraints. We show the results of some
preliminary experiments on a prototype system.
-----------------------------------------------------------------------------