-
Information extraction (IE) refers to the task of turning text documents into
a structured form, in order to make the information contained therein
automatically processable. Recently, Fagin et al. have carried out a foundational study
on rule-based IE, and introduced a formal framework based on the notion of
(document) spanner [
6,7
]. A spanner P is a function that maps a given string
(D) to a relation, i.e., a set of tuples, over its spans. A span is a pair of indices
that identify substrings of D. For example, given the string DL-2018 DL-2019,
the spans [4; 8i and [12; 16i identify the substrings 2018 and 2019, respectively.
Fagin et al. study possible representations of spanners and analyze how the use
of some algebraic operations on the relations extracted from strings in uences
the spanner expressiveness. In particular, they consider spanners de ned by
regular expressions with capture variables (a.k.a. \regex formulas ") and relational
algebra. Regex formulas di er from classical regular expressions since they allow
for mapping sub-matches of regular expressions, in the form of spans, to
variables. For example, in the regex formula xf[0 9]+g, x is a variable matching
to spans of nonempty strings consisting only of digits. Applied, for instance, to
the string DL-2018 DL-2019, it returns the (unary) relation f([4; 8i); ([12; 16i)g.
In our paper [
8
], we construct on the notion of document spanners and
propose a formal framework for coupling them with ontologies. Through this
framework we aim at structuring information extracted from text documents according
to the intensional knowledge expressed by the ontology. To this aim, we adapt
the well-known framework for Ontology-based Data Access (OBDA), in which
an ontology is mapped to an external source database through declarative
mappings, which specify the semantic relationship between the ontology vocabulary
and the data at the sources [
3,13
]. OBDA is a powerful paradigm for data access
and governance, for its ability to shift data management and integration at the
conceptual level. In OBDA, however, ontologies have been used so far only on
top of relational databases, with very few exceptions (as, e.g., [
1
]). In our paper
we thus enrich OBDA with the capability of accessing unstructured information
contained in text documents.
Our rst contribution is the notion of Ontology-based document spanning
(OBDS) system, in which an ontology is linked to text documents through
extraction assertions, which in OBDS act exactly as mapping assertions in OBDA.
In particular, an extraction assertion associates a document spanner P to a query
q speci ed over the ontology. In OBDSs queries over the ontology are conjunctive
queries (CQs), and document spanners are de ned as regex formulas extended
with the relational algebra operators union, projection, join and string selection
(the class of such spanners is studied in [
6
] and is denoted with [[RGXf[; ;1; =g]]).
An OBDS E is thus a pair hT ; Ri, where T is a Description Logic (DL) TBox
and R is a set of extraction assertions of the form
P (v1; : : : ; vn) ;
(v1; : : : ; vn)
where P (v1; : : : ; vn) is a document spanner in [[RGXf[; ;1; =g]], associated to
variables v1; : : : ; vn, and (v1; : : : ; vn) is a CQ with free variables v1; : : : ; vn.
Atoms of this CQ are built over v1; : : : ; vn, and possibly over other existential
variables and/or constants, and object terms denoting individuals \constructed"
from the spans returned by P when applied to a document (as in OBDA
mappings [
10
]). We notice that extraction assertions we have de ned correspond to a
powerful form of GLAV mapping assertions [
9,5
]. We also say that assertions are
GAV, if (v1; : : : ; vn) does not contain existential variables. An interpretation
I is a model for E w.r.t. a document D if I is a model for T , and I satis es R
w.r.t. D. As in OBDA, we adopt a sound interpretation for extraction assertions,
according to which, intuitively, satisfying R w.r.t. D means that, for each
extraction assertion in R, (t) evaluates to true in I, for each tuple t = t1; : : : ; tn
of substrings corresponding to the spans returned by P , where (t) is the CQ
in which every vi is substituted with ti (see [
8
] for details).
A second contribution of our paper is on query answering, i.e., how to
compute the certain answers to queries posed over the ontology of an OBDS system
E = hT ; Ri, i.e., those answers that hold in each model of E . We focus on CQs
and OBDS systems whose ontology is speci ed in the Description Logic (DL)
DL-LiteR [
2
]. It is well-known that in OBDA, when the ontology is in DL-LiteR
and mapping assertions are GLAV, CQ answering is rst-order rewritable, i.e.,
it can be reduced to the evaluation of a rst-order query over the
underlying database [
4
]. Therefore, the rewriting has the same expressiveness of the
database queries used in the mapping. A natural question is now whether a
similar behaviour shows up also in DL-LiteR OBDS systems, i.e., whether we
can reduce query answering to the execution of a document spanner of the same
expressiveness of the spanners in R. We positively answer to this question, by
providing an algorithm that rewrites every CQ issued over a DL-LiteR OBDS
system into a spanner belonging to [[RGXf[; ;1; =g]]. To this aim, we adapt to
OBDS a technique from OBDA [
4
]. In a nutshell: we rst split each extraction
assertion into a pair of GAV and LAV assertions; we then rewrite the query
according to the TBox by using, e.g., the PerfectRef algorithm [
2
]; we then further
rewrite the query according to the \LAV part" of R, by means of an algorithm
for view-based query rewriting, like Minicon [
11
]; nally we rewrite the query
with respect to the \GAV part" of R, essentially by unfolding the query
predicates with the spanners they are associated with. Since evaluating such spanners
is polynomial in the size of the input document, we can also conclude that CQ
answering in this setting is polynomial in data complexity.
We nally note that there is a lot of previous work on use of ontologies in IE
(see, e.g., [
12
] for a survey). To the best of our knowledge, our paper is the rst
one studying query answering over ontologies populated from text documents,
in the spirit of OBDA. Also, we believe that our OBDS framework may pave the
way for an in-depth investigation of the role of ontologies in IE.