Exploring Controlled English Ontology-Based Data Access

Abstract

Controlled languages (CLs) are subsets of natural language with minimal ambiguity (lexical, structural, or semantic) tailored to fullfil data management tasks. Recently [5, 11], they have been proposed as a means of providing natural language interfaces to databases (DBs) and to ontology-based data access systems (OBDASs) centered around the W3C standard ontology language OWL1 (Web Ontology Language) [7, 9]. CL utterances are so-to-speak ”compiled” (compositionally translated by a symbolic translation) into a formal query/ontology language expression. They have given rise to a number of applications and implementations [5, 11], among which ACE-OWL [7, 9], which maps to OWL DL and fragments of it (such as OWL-Lite). The formal underpinning of OWL DL is provided by description logics (DLs) [3, 8], in particular, OWL Lite corresponds to the DL SHIF (Actually SHIF (D), but we do not consider datatypes). Given that OBDASs may contain large amounts of data, we are interested in knowing whether querying such systems through CL interfaces scales up with the size of the data. An ODBAS can be modelled by a DL knowledge base (KB), whose information is accessed through queries belonging to some fragment of SQL. A fragment that is considered sufficiently expressive but still computationally manageable (since query answering is decidable in significant cases) is that of conjunctive queries [1]. The basic problem in this setting is (conjunctive) query answering (QA) [6], which is a form of logical entailment [3]. To evaluate the efficiency of querying through CL interfaces, we focus on the so-called data complexity of QA, i.e., the computational complexity of the problem measured in terms of the size of the data only [16]. The optimum lies in L data complexity, which is the complexity of answering SQL queries over plain databases. Data complexity beyond PTime (i.e., intractable) indicates low scalability of query answering through CL interfaces. The data complexity of query answering in SHIF , and hence in OWL Lite and ACE-OWL Lite (the fragment of ACE that maps to OWL Lite) is known to be coNP-complete [12]. Hence, CLs like ACE-OWL do not scale up with data, although they contain fragments that do. This computational behaviour depends on the language constructs they cover. In this paper we pinpoint (some of) the English constructs and a fortiori of ACE, that give rise to these computational properties. To this effect, we study a CL that maps into ALCI, a DL simpler than SHIF but with the same data complexity of query answering, and fragments thereof that are either (i) minimal w.r.t. intractability or (ii) maximal w.r.t. tractability, mirroring Pratt and Third in [13] (cf. also [14]). 1 http://www.w3.org/TR/owl-ref/

Introduction

QA over Ontologies

In an OBDAS, an ontology provides a conceptual view on the data stored in a database. Ontologies are formally underpinned by DLs [ 3 ], which structure the domain of discourse in terms of concepts (representing classes, i.e., sets of objects) and roles (representing binary relations between objects). We are interested in DLs of different expressiveness, ranging from DL-Liteu [ 6 ] to ALCI. In ALCI, concepts C and roles R are formed according to the following syntax: where A stands for a concept name (a unary predicate), P for a role name (a binary predicate) and P for its inverse. The semantics of the concept and role constructors is the standard one for DLs, see [ 3 ]. We can enrich the set of ALCI concepts, modulo the following (explicit) definitions: (i) 8R:C := :9R::C, (ii) C t C0 := :(:C u :C0), (iii) ? := :>, and (iv) 9R := 9R:>.

In a DL ontology O, intensional knowledge is specified by means of a set of (concept inclusion) assertions of the form Cl v Cr, stating inclusion (or IS-A) between the instances of the concept Cl on the left and those of the concept Cr on the right. In ALCI, Cl and Cr may be arbitrary concepts, while fragments of ALCI, such as DL-Liteu [ 6 ], can be obtained by suitably restricting the syntax for Cl and for Cr. A database (DB), expressing extensional knowledge, is a finite set D of unary and binary ground atoms of the form A(c), P (c; c0). A knowledge base (KB) is a pair hO; Di, where O is an ontology and D a DB.

As query language, we consider conjunctive queries, i.e., SELECT-PROJECT-JOIN SQL queries and tree shaped conjunctive queries (TCQs), which are those CQs that are built using only unary and binary relations and that are tree-isomorphic [ 12 ]. The query answering (QA) decision problem for (T)CQs and KBs is the (FOL) entailment problem stated as follows: given a KB hO; Di, a sequence c of constants and a (T)CQ q, check whether there exists a grounded substitution of the free variables of q with c s.t. O [ D j= q , i.e., whether O [ D (when seen as a FOL theory) entails the grounding of q (seen as a FOL open formula) by . We are interested in the data complexity of QA, namely, in its computational complexity when we consider D as the only input of the problem. 3

Expressing QA in Controlled English

Given an ontology language L and a query language Q, to express QA in controlled English we: (i) Define a grammar GL and a compositional translation ( ) for the corresponding controlled declarative fragment L(GL) s.t. (L(GL)) = L. (ii) Define a grammar GQ and a compositional translation 0( ) for the corresponding controlled interrogative fragment L(GQ) s.t. 0(L(GQ)) = Q. Following formal semantics terminology we call such ontology/query language expressions the meaning representations (MRs) of the CL utterance.

In [ 4, 15 ], we have shown how to express the DL DL-Liteu and TCQs, for which QA is in L [ 6 ], with the CLs Lite-English and GCQ-English, respectively. We want now

NP ! Det Nom

VP ! is a Nom VP ! is TV by NP NP ! Pro Relp VP

VP ! IV VP ! is Neg TV by NP NP ! Pro

VP ! is Neg a Nom Nom ! Nom Relp VP Nom ! Adj Nom

VP ! VP Crd VP Nom ! Nom Crd Nom Nom ! N (VP) := (NP)( (TV)) (VP) := (Crd)( (VP))( (VP)) (S) := (NP)( (VP)) (VP) := (Neg)( (NP)( (TV))) (VP) := (Neg)( (Adj)) (VP) := (Neg)( (Nom)) (VP) := (Neg)( (IV)) (VP) := (Adj) (NP) := (Pro) (VP) := (IV) (VP) := (Nom) (NP) := (Det)( (Nom)) (NP) := (Pro)( (Relp)( (VP))) (Nom) := (N) (Nom) := (Nom)( (Relp)( (VP))) (Nom) := (Crd)( (Nom))( (Nom)) (Nom) := (Adj)( (Nom)) Pro ! anybody (Pro) := C: C0:C v C0 Pro ! nobody (Pro) := C: C0:C v :C0 Crd ! and (Crd) := C: C0:C u C0 Relp ! who (Relp) := C:C Neg ! not (Neg) := C::C Pro ! everybody (Pro) := C:> v C Det ! some (Det) := R: C:9R:C Det ! no (Det) := C: C0:C v :C0

Pro ! somebody (Pro) := Pro ! nobody (Pro) := Crd ! or (Crd) := Relp ! who (Relp) := Pro ! only (Pro) := Pro ! nobody (Pro) := Det ! every (Det) :=

R:9R R::9R C: C0:C t C0 C: C0:C:C0 R: C:8R:C C:C v ?

C: C0:C v C0 to know which fragments of ACE-OWL are (i) maximal w.r.t. tractable data complexity (i.e., in PTime), and hence scale up with data, and (ii) minimal w.r.t. intractable data complexity (i.e., coNP-hard), and hence do not scale up.

Figure 1 introduces DL-English’s grammar GDL. Following DL conventions [ 3 ], we associate (and hence map) the non-recursive word categories N, Adj and IV to atomic concepts. Category TV is associated to role names. Recursive constituents, by contrast, are associated to arbitrary concepts. For reasons of simplicity and space, we disregard morphology and polarity issues. We also omit specifying the (open) class of content words. An example of a sentence recognized by DL-English (we spell out its MR underneath) is:

No man who runs some business that does not make some money is a businessman.

Man u 9run:(Business u :(9make:Money)) v :Businessman

We now turn to the computational properties of each of the constructs in isolation of DL-English. We do it by essentially restricting the kind of right (i.e., Cr) and left (i.e., Cl) concepts we may express. All utterances comply with the sentence patterns ”every l r” and ”everybody who l r”.

The constituents l and r map to, respectively, left and right concepts, while sentences map to IS-A assertions of the form Cl v Cr. We consider in this paper only 8 out of all possible combinations obtained by allowing in Cl and Cr some subset of the DL constructs in the upper part of Figure 2, giving rise to the family fIS-Aigi2[0;7] of CLs shown in Figure 2. The basic kind of assertion they all express is IS-A among atomic concepts, viz., A v A0, captured by IS-A0.

The complexity result for IS-A0 follow from the fact that Lite-English subsumes it. For all the other fragments, the complexity lower bounds follow from the results in [ 6 ]. The upper bounds for the CLs IS-Ai, for i 2 f2; 3; 4g, follow from results by [ 10 ] for the DL E L, which subsumes the DL assertions they express. Membership in NL for IS-A1 follows by reducing QA over IS-A1 KBs to linear datalog program evaluation, which is well-known to be in NL (w.r.t. data complexity) [ 1 ].

:A Fragment

IS-A0 IS-A1 IS-A2 IS-A3 uAn tAn

A1 u IS-A4 IS-A5 IS-A6 IS-A7

Constituent f

Nomf , VPf

TV some Nomf , TV somebody who VPf TV by some Nomf , TV by somebody who VPf

TV only VPf , TV only who VPf

TV something, TV somebody

Adj Nomf ; Nomf who VPf Nomf and Nomf ; VPf and VPf

VPf or VPf is not Adj, does not IV, is not a Nomf

VPf ! is a Nomf j IV j is Adj

Nomf ! N

;

VPf ! is a Nomf j IV j is Adj j VPf and VPf

Nomf ! N j Adj Nomf j Nomf and Nomf

VPf ! is a Nomf j IV j is Adj j VPf and VPf

Nomf ! N j Nomf and Nomf

Nomf ! N

Assertions A v A1 u uAn

A v 8P :A uAn v 8P :(A1 u 9P :A v A1 u uAn 9P :A v A1 u

uAn

A1 u 9P :(A1 u

A v 9P uAn v A1 u

uAn) v A1 u 8P :A v A1 u

A v A1 t :A v A1 u

uAn tAn uAn

Sample Sentence(s) Data Complexity every businessman is a cunning man in L every herbivorous eats only herbs NL-complete uAm) every Italian man drinks only strong coffee PTime-complete anybody who murders some person PTime-complete

is a heartless killer, anybody who is loved by some person

is a happy person, every driver drives something uAm every cruel man is a bad man, PTime-complete uAm anybody who runs some bankrupt company

is a bad businessman anybody who values only money is a coNP-complete

greedy person every mammal is male or is female coNP-complete anybody who is not selfish is a reasonable coNP-complete

person Data Complexity

Lite English EL-English DL-English ACE-OWL

in L PTime-complete coNP-complete coNP-hard

We can now individuate the constructs of DL-English, and a fortiori of any CL expressing a coNP-hard ontology language such as SHIF (as does ACE-OWL) that negatively affect the scalability of CL interfaces to ODBASs, namely: – ”only” in subject position (coNP-hardness of IS-A5), – disjunction in predicate position (coNP-hardness of IS-A6), – negation in subject position (coNP-hardness of IS-A7).

They also allow us to identify maximal CLs contained in DL-English (and a fortiori ACE-OWL) w.r.t. scalability (i.e., tractable data complexity). By merging the (tractable) fragments IS-Ai, for i 4, we essentially express the E LI ontology language, with syntax (notice that the assertion A v 8P :A0 is equivalent to 9P :A v A0): That is, the DL where negation- and disjunction free existential concepts are allowed to arbitrarily nest on both sides of v. E LI induces a PTime-complete fragment of DLEnglish, that we term EL-English, which captures most of the constraints and axioms of real-world large-scale biomedical ontologies such as GALEN or SNOWMED [ 2 ]. We can define EL-English top-down pretty easily by removing from GDL the grammar rules for negation, disjunction, and universal quantification, and the negative function words. In such a CL arbitrary sentence subordination (and relatives), in combination with, existential quantification and conjunction among VPs or Noms is allowed. Universal quantification is highly controlled and negation and disjunction are ruled out.

Conclusions

We have studied the computational complexity of querying OBDASs in controlled English. Optimal (i.e., L) data complexity is attained with Lite-English (expressing DL-Liteu) and GCQ-English (expressing TCQs) [ 4, 15 ]. Relaxing, however, the constraints put on negation, disjunction, universal determiners, and pronouns, until the components in sentence subjects and predicates become symmetrical, as in DL-English or more expressive CLs, yields coNP-hardness. In particular, data access in ODBASs through CL interfaces is intractable when coverage in declarations is extended to negation and universal quantification in subject NPs, or when we allow disjunction in predicate VPs. We also identify a maximal (scalable) CL, EL-English, which is in PTime w.r.t. data complexity.

Acknowledgements. We thank Raffaella Bernardi and Norbert Fuchs for discussions and criticism regarding earlier versions of this paper.

References

1. S. Abiteboul , R. Hull , and V. Vianu . Foundations of Databases. Addison Wesley , 1995 .

2. F. Baader , S. Brandt , and C. Lutz . Pushing the E L envelope . In Proc. of IJCAI 2005 .

3. F. Baader , D. Calvanese , D. Nardi , P. Patel-Schneider , and Deborah McGuinness . The Description Logic Handbook . Cambridge University Press, 2003 .

4. R. Bernardi , D. Calvanese , and C. Thorne . Lite Natural Language . In Proc. of the 7th Int. Workshop on Computational Semantics (IWCS-7) , 2007 .

5. A. Bernstein , E. Kaufman, A. Go¨hring, and C. Kiefer . Querying ontologies: A controlled English interface for end-users . In Proc. of ISWC 2005 .

6. D. Calvanese , G. De Giacomo, D. Lembo , M. Lenzerini , and R. Rosati . Data complexity of query answering in description logics . In Proc. of KR 2006 .

7. N. E. Fuchs and K. Kaljurand . Mapping Attempto Controlled English to OWL DL. In Demos and Posters of the 3rd European Semantic Web Conf . (ESWC 2006 ).

8. I. Horrocks , P. F. Patel-Schneider , and F. van Harmelen. From SHIQ and RDF to OWL: The making of a web ontology language . J. of Web Semantics , 1 ( 1 ): 7 - 26 , 2003 .

9. K. Kaljurand and N. E. Fuchs . Verbalizing OWL in Attempto Controlled English . In Proc. of OWLED 2007 .

10. A. Krisnadhi and C. Lutz . Data complexity in the E L family of description logics . In Proc. of LPAR 2007 .

11. S. Mador-Haim , Y. Winter , and A. Braun . Controlled language for geographical information system queries . In Proc. of Inference in Computational Semantics , 2006 .

12. M. Ortiz , D. Calvanese , and T. Eiter . Data complexity of query answering in expressive description logics via tableaux . J. of Automated Reasoning , 41 ( 1 ): 61 - 98 , 2008 .

13. I. Pratt and A. Third . More fragments of language . Notre Dame J. of Formal Logic , 2005 .

14. M. Slavkovik . Deep analysis for an interactive question answering system . Master's thesis , KRDB Research Centre, Free University of Bozen-Bolzano, 2007 .

15. C. Thorne . Expressing aggregate queries over DL-Lite ontologies with controlled English . In Proc. of the ESSLLI 2008 Student Session , 2008 .

16. M. Y. Vardi . The complexity of relational query languages . In Proc. of STOC'82.