Sébastien Ferré
email: sebastien.ferre@irisa.fr

Sebastian Rudolph
email: sebastian.rudolph@kit.edu

Advocatus Diaboli -Exploratory Enrichment of Ontologies with Negative Constraints

With the persistent deployment of ontological specifications in practice and the increasing size of the deployed ontologies, methodologies for ontology engineering are becoming more and more important. In particular, the specification of negative constraints is often neglected by the human expert, whereas they are crucial for increasing an ontology's deductive potential. We propose a novel, arguably cognitively advantageous methodology for identifying and adding missing negative constraints to an existing ontology. To this end, a domain expert navigates through the space of satisfiable class expressions with the aim of finding absurd ones, which then can be forbidden by adding a respective constraint to the ontology. We give the formal foundations of our approach, provide an implementation, called Possible World Explorer (PEW) and illustrate its usability by describing prototypical navigation paths using the example of the well-known pizza ontology.

Introduction

Ontologies -logical descriptions of a domain of interest -are at the core of Semantic Technologies. Expressive ontology languages like OWL allow for very precise specifications of semantic interdependencies between the notions describing a domain of interest. While it has been argued that "a little semantics goes a long way" and lightweight formalisms provide for better scalability properties, it is also widely accepted that expressive formalisms are superior in terms of modeling power and the capability of deriving implicit knowledge, thereby allowing for a more intelligent way of handling information.

From the viewpoint of formal semantics, the axioms of an OWL ontology can be seen as conditions or constraints which a possible world has to satisfy for being in line with what the ontology modeler has specified to be "true" in the considered domain. Thereby, one can distinguish between positive constraints, which specify what must be necessarily true, and negative constraints declaring what is impossible. 3 It has often been noted that positive constraints -such as class memberships, class and role hierarchies, or domain and range restrictionsare more salient and graspable to human beings and are preferably specified by modelers, whereas typical negative constraints -like class or role disjointnessare often neglected. However, negative constraints are crucial for exploiting the full deductive potential of expressive ontological modeling. In particular, they are essential for causing inconsistencies, being a helpful feature for many ontology management tasks, e.g. detecting modeling errors in the course of ontology creation and refinement [START_REF] Haase | Consistent evolution of OWL ontologies[END_REF], repairing mappings between two ontologies [START_REF] Meilicke | Repairing ontology mappings[END_REF] or revising ontologies interactively [START_REF] Nikitina | Interactive ontology revision[END_REF].

In order to overcome this problem, many automated techniques have been designed to extract negative constraints from ontologies themselves or other sources, such as texts [START_REF] Schlobach | Debugging and semantic clarification by pinpointing[END_REF][START_REF] Völker | Learning disjointness[END_REF][START_REF] Meilicke | Learning disjointness for debugging mappings between lightweight ontologies[END_REF][START_REF] Fleischhacker | Inductive learning of disjointness axioms[END_REF]. The majority of these techniques rely on heuristics and machine learning methods whence their results are not entirely reliable and usually need to be inspected manually. Moreover, the mentioned approaches are restricted to disjointness, the simplest form of negative constraints. On another note, in the course of interactive ontology completion strategies based on Formal Concept Analysis [START_REF] Rudolph | Exploring relational structures via FLE[END_REF][START_REF] Baader | Completing description logic knowledge bases using formal concept analysis[END_REF][START_REF] Rudolph | Acquiring generalized domain-range restrictions[END_REF], negative constraints are naturally acquired next to positive ones. As a downside, these techniques are rather expensive in terms of user interaction and tend to patronize the expert by forcing her to just answer a prescribed row of questions.

We propose to approach the problem from a different angle by providing more freedom to the domain expert and representing the task of specifying negative constraints in a cognitively apt (and, hopefully, interesting or even playful) way. This is achieved by letting the expert navigate the possibilities left open by the currently specified ontology, using a faceted browsing approach, and discover absurd configurations. In a sense, the modeler explores the "Platonic universe" where everything ontologically possible also exists. This way, configurations which are practically impossible can be identified, turned into negative constraints, and added to the ontology.

The paper is structured as follows. In Section 2, we lay out the basic idea of our methodology. Section 3 provides syntax and semantics of the description logic underlying OWL in a condensed way, while Section 4 introduces further formal notions needed for our approach. Section 5 describes our navigation approach on a technical level and establishes properties which ensure its adequacy. In Section 6, we introduce the Possible World Explorer (PEW), a tool which implements the proposed methodology and in Section 7 we illustrate its usefulness and usability by describing exemplary runs of it. Section 8 concludes and describes avenues for future work. An extended version of this paper including full formal proofs is available as technical report [START_REF] Ferré | PEW! PEW! Tech. rep[END_REF].

The Advocatus Diaboli Methodology

Here we give a non-technical overview of our envisioned methodology for the specification of negative constraints by exploring possible worlds.

As a starting point, we assume that an OWL ontology has been created by stipulating the used vocabulary and possibly arranging classes and properties in taxonomies. It is not essential that the ontology contains individuals, our method works equally well for non-populated ontologies. Also, the ontology may or may not already contain axioms beyond taxonomic relationships.

According to the model-theoretic semantics, an ontology can be seen as a set of constraints characterizing possible worlds (the models of the ontology). Adding axioms to an ontology results in strengthening these constraints and thereby "ruling out" models.

Our methodology can be seen as an exploration of the possible worlds admitted by an ontology. Thereby, a domain expert starts to describe an individual of one of these possible worlds by specifying its class memberships and relationships to other individuals. This specification process is supported by an interface in the spirit of faceted browsing, which naturally constrains the specification process in a way that no descriptions can be constructed which would contradict the ontology. In other words, the navigation-like stepwise refinement of the description of a possible individual ensures that an individual matching this description indeed exists in at least one of the models of the ontology. In this sense, the proposed methodology can indeed be seen as an "exploration of possible worlds".

The actual task of the domain expert is now to construct descriptions which are possible according to the ontology but absurd given the experts domain knowledge. That is, the domain expert is supposed to assume the role of the "devils advocate" by actively trying to construct situations which are impossible according to his/her knowledge of the domain, thereby showing that the given ontology is underconstrained. Once such a problematic description has been constructed, it can be converted into an axiom which exactly prohibits this situation. By adding this axiom to the ontology, the just constructed absurd description is made impossible and every model featuring such a situation is excluded from the possible worlds.

From a cognitive viewpoint, the particular twist of this methodology is that it facilitates the specification of negative constraints by staying on a positive, scenario-like level, by exploring what is (logically) possible, pushing the boundaries of what is conceivable, and trying to cross them by constructing "nonsensical" descriptions. Arguably, this is much easier and more intuitive than the task of directly coming up with negative constraints.

Preliminaries

Although the proposed methodology is suitable for any sufficiently expressive logical formalism, we focus our consideration on the OWL Web Ontology Language [START_REF] Owl Working Group | OWL 2 Web Ontology Language: Document Overview[END_REF] as the currently most prominent expressive ontology language. 4Table 1. Syntax and semantics of role and class constructors in SROIQ. Thereby a denotes an individual name, R an arbitrary role name and S a simple role name. C and D denote class expressions.

Name

Syntax Semantics inverse role

R - { x, y ∈ ∆ I × ∆ I | y, x ∈ R I } universal role U ∆ I × ∆ I top ⊤ ∆ I bottom ⊥ ∅ negation ¬C ∆ I \ C I conjunction C ⊓ D C I ∩ D I disjunction C ⊔ D C I ∪ D I nominals {a} {a I } univ. restriction ∀R.C {x ∈ ∆ I | x, y ∈ R I implies y ∈ C I } exist. restriction ∃R.C {x ∈ ∆ I | for some y ∈ ∆ I , x, y ∈ R I and y ∈ C I } Self class ∃S.Self {x ∈ ∆ I | x, x ∈ S I } qualified number n S.C {x ∈ ∆ I | #{y ∈ ∆ I | x, y ∈ S I and y ∈ C I } ≤ n} restriction n S.C {x ∈ ∆ I | #{y ∈ ∆ I | x, y ∈ S I and y ∈ C I } ≥ n}
The OWL DL version of the current OWL standard is based on the very expressive description logic SROIQ [START_REF] Horrocks | The even more irresistible SROIQ[END_REF]. For a description of the relationship between OWL and the underlying description logics, the reader is referred to [START_REF] Hitzler | Foundations of Semantic Web Technologies[END_REF] or [START_REF] Rudolph | Foundations of description logics[END_REF]. In this paper we will use description logic notation for its brevity. Thus, we briefly recap syntax and semantics of the description logic SROIQ, although we will only actively work with a restricted sublanguage of it thereafter.

Let N I , N C , and N R be finite, disjoint sets called individual names, class names and role names respectively, 5 with N R = R s ⊎ R n called simple and non-simple roles, respectively. These atomic entities can be used to form complex classes and roles in the usual way (see Table 1). A SROIQ-knowledge base6 is a tuple (T , R, A) where T is a SROIQ-TBox, R is a regular SROIQ-role hierarchy 7 and A is a SROIQ-ABox containing axioms as presented in Table 2. The semantics of SROIQ is defined via interpretations I = (∆ I , • I ) composed of a non-empty set ∆ I called the domain of I and a function • I mapping individuals to elements of ∆ I , classes to subsets of ∆ I and roles to subsets of ∆ I × ∆ I . This mapping is extended to complex roles and classes as displayed in Table 1 and finally used to evaluate axioms (see Table 2). We say I satisfies a knowledge base KB = (T , R, A) (or I is a model of KB , written: I |= KB ) if it satisfies all axioms of T , R, and A. We say that a knowledge base KB entails an axiom α (written KB |= α) if all models of KB are models of α. Finally, a knowledge base KB is satisfiable if it has a model and a class C is called satisfiable w.r.t. a knowledge

R1 • • • • • Rn ⊑ R R I 1 • • • • • R I n ⊆ R I RBox R Dis(S, T ) S I ∩ T I = ∅ C ⊑ D C I ⊆ D I TBox T C(a) a I ∈ C I ABox A R(a, b) (a I , b I ) ∈ R I a . = b a I = a I a . = b a I = b I base KB if

Formal Foundations

We now define a subclass of OWL class expressions which we deem particularly intuitive to deal with from a cognitive perspective as they essentially represent (alternatives of) existing structures, while negations are only used at an elementary level. 8 To see that this choice is reasonable, note that humans would normally have no problems with handling the class of non-smokers or childless persons, while classes such as non-(persons having a big dog and a small cat) occur unnatural, contrived and are harder to cognitively deal with. Next, the set CI of cognitively intuitive class expressions is inductively defined as follows:

1. every simple class expression is in CI, 2. for C 1 , C 2 ∈ CI, C 1 ⊓ C 2 and C 1 ⊔ C 2 are in CI, 3. for r ∈ N R and C ∈ CI, ∃r.C and ∃r -.C are in CI.

The set CI[X] of pointed CI class expressions denotes CI class expressions with the symbol X occurring exactly once in the place of an unnegated class name.

In words, CI class expressions allow for the description of situations: existing objects, their interrelations and their properties (in terms of being (non)members of atomic classes, (not) participating in a relationship, or (not) being identical to a named individual). Thereby, the structure of the axioms enforces that only tree-like relationships can be described. Moreover, the use of disjunction allows for specifying alternatives for parts of the situation descriptions.

Pointed class expressions are used to put a focus on a subexpression of a class expression. This focus will serve as a marker to indicate a point in the expression where new subexpressions can be attached. Consequently, given a pointed CI class expression C(X) and a CI class expression D, we write C(D) for the class expression C(X)[D/X] obtained by replacing the occurrence of X in C(X) by D. The following proposition is an easy consequence of the observation that by construction, X occurs in a position with positive polarity. Let KB be a knowledge base containing just the following two axioms: (A1) ∃colonyOf -.⊤ ⊓ EUCountry ⊑ ⊥ stating that EU countries must not have colonies and the axiom (A2) ∃colonyOf -.⊤ ⊑ Country expressing that only countries may have colonies. Then, considering the pointed class expression Country ⊓ ∃colonyOf.X has Country as a necessary adjunct since (A2) would render Country ⊓ ∃colonyOf.¬Country unsatisfiable. On the other hand, EUCountry is not a possible adjunct, since Country ⊓ ∃colonyOf.EUCountry is not satisfiable.

Clearly, the sets of possible and necessary adjuncts of a pointed class expression provide useful information on how the expression can be reasonably extended and what extending adjuncts would be implied anyway, both taking the provided knowledge base into account. Still, in specific cases, with disjunctive information being involved, poss KB (C(X)) might not quite capture the needed information, as illustrated by the following example. To exclude such unwanted cases, we introduce the notion of balancedness (Definition 4) as a desired property of class expressions. Intuitively, a class expression is balanced, if all alternatives described by unions can possibly occur. Toward the formal definition, we first have to introduce the notion of prunings (Definition 3). By pruning a pointed class expression, we specialize it by removing disjunctive side branches, thus enforcing that the disjunctive branch in which X is located must be "realized".

C = C ′ (D 1 ⊔ D 2 )
. Then, we call the occurrence of By definition, full balancedness of a class can be checked by a twofold class satisfiability test for each disjunctive subexpression, thus the number of necessary class satisfiability checks is linearly bounded by the size of the class expression.

D 1 ⊔ D 2 in C balanced if both prune(C ′ (X))[D 1 /X] and prune(C ′ (X))[D 2 /X]
It is rather easy to see that by restricting to fully balanced class expressions, we do not lose anything in terms of expressivity, since for any satisfiable class we find an equivalent one which is fully balanced by pruning away the fake disjuncts. These findings justify our suggestion to restrict the possible adjuncts for a pointed class expression to those which would not just maintain its satisfiability, but also its balancedness.

Navigation

We now describe the navigation operations of our class exploration methodology on an abstract level as modifications of a pointed class expression C(X).

(M) Moving the focus. For moving the focus, one picks an occurrence of a subclass D which is not in the scope of a negation. Then we obtain C ′ (X, Y ) from C(X) by replacing the chosen occurrence of D by Y if D = ⊤ and by D ⊓ Y otherwise. Thereafter, we obtain C ′′ (Y ) from C ′ (X, Y ) by replacing E ⊓ X by E if X occurs in such a conjunction, or otherwise replacing X by ⊤. Finally, we obtain the result C new (X) of this operation from C ′′ (Y ) by substituting Y with X. (D) Deleting subexpression at focus. This operation is applicable if X occurs in C(X) inside a conjunction E ⊓ X. In this case, the result C new (X) is obtained by replacing E ⊓ X by X. (I) Inserting a disjunction. This operation is applicable if X occurs in C(X) inside a conjunction E ⊓ X. In this case, the result C new (X) is obtained by replacing E ⊓ X by E ⊔ X. (E) Extending the expression. Pick a class expression D ∈ poss KB (C(X))

and obtain C new (X) by replacing X with ∃r (-) .X in case D = ∃r (-) .⊤ or otherwise with D ⊓ X.

We now provide two desirable properties, which justify the choice of the navigation steps introduced above. The not overly intricate but in places a bit verbose and tedious full proofs can be found in [START_REF] Ferré | PEW! PEW! Tech. rep[END_REF]. First, we show that in the course of navigation, only fully balanced classes can be obtained if one starts from a fully balanced pointed class expression.

Proposition 3. Each of the described navigation steps (M), (D), (I), and (E) results in a fully balanced pointed class expression, if it is applied to a fully balanced pointed class expression.

The second proposition shows that the proposed navigation methodology is complete in the sense that we can construct all potentially "interesting" class expressions.

Proposition 4. Each fully balanced pointed CI class expression can be constructed by a sequence of navigation steps starting from X.

Summing up, our navigation paradigm is tuned in a way that favors construction of "meaningful" (in terms of satisfiability and balancedness) class descriptions but does not restrict expressivity otherwise.

The Possible World Explorer

We have developed a prototype of the Possible World Explorer (PEW9 for short) that allows for both the exploration of possible worlds, and the assertion of negative axioms to eradicate possible worlds ("pew pew!"). On one hand, PEW is implemented on top of the OWL API10 for handling ontologies, and on the Her-miT reasoning engine [START_REF] Motik | Hypertableau reasoning for description logics[END_REF] for checking the satisfiability of class expressions. On the other hand, PEW reuses the principles and user interface of SEWELIS11 [START_REF] Ferré | Semantic search: Reconciling expressive querying and exploratory search[END_REF] for the interactive construction and display of class expressions and their possible adjuncts. The sources, executable, and screencasts of the system are available at http://www.irisa.fr/LIS/softwares/pew/.

Figure 1 shows a screenshot of PEW's user interface. It is composed of a toolbar (T) at the top, a class box (C) at the top left, an instance box (I) at the bottom left, and an adjunct box (A) on the right. The class box (C) displays the current pointed class expression C(X), where the subexpression at the focus X is highlighted. The known instances of the class expression C(⊤) are listed in the instance box (I). The possible adjuncts of C(X) are displayed in the adjunct box (A). Class names are displayed as a tree according to the underlying ontology's class hierarchy, and unqualified existential restrictions are displayed as a tree according to the property hierarchy. For each possible adjunct D ∈ poss KB (C(X)), both D and ¬D are displayed, except for the necessary D ∈ nec KB (C(X)), for which only D is displayed but in a larger font. For the concrete syntax of the class expression and adjuncts, both DL notation and Manchester syntax are available. For better readability of complex expressions, we use indentation instead of brackets, and syntax highlighting (foreground color) to distinguish between class, role, and individual names.

From Figure 1, we can conclude a number of things about the pizza ontology 12 . From the class box, we conclude that a pizza may have no topping. From the emptiness of the instance box, we conclude that there is no known individual pizza without topping. From the adjunct box, we further conclude that such a pizza must be some food, that it must have some base as an ingredient, but that it may also be a country, and that it may have no country of origin.

Navigation from one (pointed) class expression to another is entirely performed in an interactive way. Double-clicking an adjunct extends the class expression by inserting it at the focus. Alternatively, adjuncts can be found by auto-completion in the text fields (one at the focus in the class box, and another above the adjunct box). The focus can be moved simply by clicking on various parts of the class expression. The contextual menu of the class box (C) provides the additional navigation steps: inserting a disjunction, and deleting the subexpression at focus. The toolbar (T) provides navigation in the history of class expressions, as well as the update of the ontology. The button "Exclude" adds the axiom C(⊤) ⊑ ⊥ to the ontology, in order to rule out models in which the current class expression has instances. Figure 1 displays a situation where this operation would make sense. To provide feedback about the update, the focus background color switches from green (satisfiable class) to red (unsatisfiable class). In the case where the update would make the ontology inconsistent, the button "Exclude" triggers an error message. Finally, the button "Save" saves the updated ontology.

The current implementation is rather naive, and optimization is left for future work. For information, we here give the nature and number of performed reasoning tasks (OWL API calls to reasoner methods). First, the hierarchy of simple class expressions has to be computed, which amounts to 1 call to getInstances for the top class, 1 call to getSubClasses for each named class, and 1 call to getSubObjectProperties for each named role. Then, at each navigation step, the known instances of the class expression C(X) are computed with 1 call to getInstances, and the possible adjuncts by checking the possibility and necessity of C(D), for each positive simple class expression D. Checking possibility amounts to 1 + 2d call to isSatisfiable, where d is the number of unions in the class expression; and checking necessity amounts to 1 call to isSatisfiable.

An Example Scenario

In this section, we describe an example scenario of exploration and completion of the pizza ontology. This ontology has the advantage of being well-known, covering a large subset of OWL constructs, and being representative for OWL ontologies. While the pizza ontology is often referred to and was subject to a number of refinements, we found in our exploration a number of unexpected possible worlds, and hence missing axioms. The following scenario describes a non-exhaustive exploration, and illustrates various situations that may arise.

First Steps in the Ontology

After launching PEW on the pizza ontology, the initial pointed class expression is C(X) = X, the instance box displays the list of all named individuals, and the adjunct box displays all simple class expressions. The latter means that every simple class and its complement are satisfiable, which generally holds in ontologies. Without prior knowledge, the user can then discover that the ontology is about food (in particular pizzas, pizza bases and pizza toppings), countries, and spiciness. The possible roles are "has ingredient" (refined into "has base" and "has topping"), "has spiciness", "has country of origin", and their inverses. Only 5 named individuals exist, namely for countries.

Class Exploration

In order to better understand the possible interactions between classes and properties, the user decides to navigate to each named class to discover what an instance of that class can be. For example, by selecting the adjunct Country, the pointed class expression becomes Country ⊓ X (see Figure 2). The instance box says there are 5 known countries, namely America, England, France, Germany, and Italy. Surprisingly, the adjunct box says that a country can be some food (possible adjunct Food), or not (possible adjunct ¬Food). This implies we can further select the adjunct Food to reach the satisfiable class expression Country ⊓ Food ⊓ X. Obviously, such an individual should not be possible, and we exclude this possibility by pushing the "Exclude" button, which has the effect of adding the axiom Country ⊓ Food ⊑ ⊥ to the ontology. This illustrates the claimed fact that even very basic negative constraints such as disjointness axioms are often missing in ontologies. On the contrary, we found no missing positive axiom like subclass axioms.

Navigating back to Country ⊓ X, the user can verify that a country cannot anymore be an instance of another class. However, looking at possible roles, she discovers that a country can not only be the country of origin of something (adjunct ∃hasCountryOfOrigin -.⊤), which is fine, but can also have a country of origin (adjunct ∃hasCountryOfOrigin.⊤), and a spiciness. Those two undesirable possibilities can be ruled out by selecting an unexpected adjunct, and asserting a negative axiom with the "Exclude" button, and by repeating this sequence on the other unexpected adjunct. Note that selecting the two adjuncts simultaneously, and then asserting an axiom would not be equivalent because this would only exclude countries that have both a country of origin and a spiciness. Yet, it is possible to use only one axiom provided a class union is used between the two unexpected adjuncts. At this stage, the user can see no more undesirable adjuncts for countries, and move to other named classes.

Looking at food (C(X) = Food ⊓ X), the only undesirable adjunct is that some food can be the country of origin of something, which the user excludes. Looking at pizzas, she decides to exclude the possibility for a pizza to be an ingredient. So far, we have only excluded positive possibilities (e.g., a pizza can be an ingredient), but it is also possible to exclude negative possibilities. From the adjunct box, the user discovers that, while a pizza must have some ingredient and some base (the simple class ¬∃hasBase.⊤ is not a possible adjunct), it may have no topping (possible adjunct ¬∃hasTopping.⊤). This can be excluded simply by selecting the negative adjunct (instead of the positive one), and asserting the axiom Pizza ⊓ ¬∃hasTopping.⊤ ⊑ ⊥ (see Figure 1), which is equivalent to Pizza ⊑ ∃hasTopping.⊤ (every pizza has a topping).

Finally, looking at spiciness (degrees), the user excludes the following possibilities: a spiciness that has a country of origin, a spiciness that is the country of origin of something, and a spiciness that has a spiciness (degree). After those exclusions, a spiciness can only be the spiciness of something. The class Spiciness has three subclasses: Hot, Medium, and Mild. Selecting any of those classes shows that no other class is possible simultaneously, which means that disjointness axioms have already been asserted between them.

Exploring Roles

When exploring roles, we investigate for each role what can be at their range and domain. Class exploration has covered axiom schemas A ⊓ B ⊑ ⊥, A ⊓ ∃r.⊤ ⊑ ⊥ and A ⊓ ¬∃r.⊤ ⊑ ⊤. Here, we will cover axiom schemas ∃r.⊤ ⊓ ¬A ⊑ ⊥ and ∃r.¬A ⊑ ⊥, which correspond, respectively, to domain and range axioms.

Looking at things that have a country of origin (with focus on the range, i.e., C(X) = ∃hasCountryOfOrigin.X), the user finds that the country of origin may be not a country (adjunct ¬Country). This means that the range axiom for role hasCountryOfOrigin is missing. It can be added by selecting the undesirable adjunct, and asserting the axiom ∃hasCountryOfOrigin.¬Country ⊑ ⊥ which is equivalent to ⊤ ⊑ ∀hasCountryOfOrigin.Country.

Inspecting things having a spiciness (C(X) = ∃hasSpiciness.⊤⊓X) with focus at the domain, it appears that those things may not be food (adjunct ¬Food). This can be excluded by asserting the axiom ∃hasSpiciness.⊤ ⊓ ¬Food ⊑ ⊥, which is equivalent to ∃hasSpiciness.⊤ ⊑ Food, and defines a domain axiom.

Further Exploration

In this section, we provide an additional example to show that our approach does not only apply to simple interactions between named classes and roles. The class Pizza has a number of subclasses that are generally defined through equivalent classes axioms as pizzas satisfying certain criteria. For example, there is the VegetarianPizza class, and obviously it should not be possible to find a vegetarian pizza that contains some meat or fish as an ingredient. Following the advocatus diaboli approach, this is exactly what we are going to try and find. Starting from a vegetarian pizza (C(X) = VegetarianPizza ⊓ X), we find that it may (and must) have some ingredient (adjunct ∃hasIngredient.⊤). By selecting this adjunct, we reach the class expression C(X) = VegetarianPizza⊓ ∃hasIngredient.X, with the focus on the ingredient. As possible ingredients, we find only food, subdivided into pizza base and pizza topping. Under the class PizzaTopping, we find that both subclasses MeatTopping and FishTopping are possible! It is even possible to reach a vegetarian pizza that has both meat and fish as ingredients. The two undesirable possibilities can be excluded at once by navigating to the satisfiable and balanced class VegetarianPizza ⊓ ∃hasIngredient.(MeatTopping ⊔ FishTopping) (see Figure 3), and pushing the Exclude button. Looking at the ontology, we do find that a vegetarian pizza is defined as a pizza that contains neither meat nor fish. The problem is that in the respective axiom, the role "has topping" was used instead of the more general "has ingredient". Obviously, a vegetarian pizza should have no meat or fish, no matter what part of the pizza contains it!

Conclusion and Future Work

We have proposed an intuitive methodology for adding negative constraints to OWL ontologies in an exploratory way. To this end, we devised and implemented an interaction paradigm for constructing intuitive satisfiable class expressions in an interactive way reminiscent of faceted browsing, which-if found to be absurdcan be turned unsatisfiable by adding a corresponding negative constraint to the underlying ontology.

Future work on this subject clearly includes scalability and usability investigations and improvements. For seamless navigation and editing, the underlying reasoning steps must be performed in near-realtime which poses some restriction on the computational intricacy of the considered ontology. In order to enlarge the scope of applicability of our method, we will optimize PEW in terms of minimizing OWL API calls.

On the usability side, next to thorough user studies, we will further enrich the tool with further functionality beyond mere exclusion of unwanted class expressions. Ultimately, we plan to provide PEW as a Protégé plugin.

Definition 1 .

 1 Given sets N C , N R , N I of atomic class names, atomic role names and individual names, respectively, simple class expressions are class expressions of one of the forms A, ¬A (with A ∈ N C ), ∃r.⊤, ¬∃r.⊤, ∃r -.⊤, ¬∃r -.⊤ (for r ∈ N R ), {o}, ¬{o} (for o ∈ N I ).

Proposition 1 .

 1 Let KB be a knowledge base, let D and D ′ be arbitrary class expressions and let C(X) be a pointed CI class expression. Then KB |= D ⊑ D ′ implies KB |= C(D) ⊑ C(D ′ ). Definition 2. Given a knowledge base KB and a pointed CI class expression C(X), we call C(X) satisfiable w.r.t. KB , if C(⊤) is satisfiable w.r.t. KB . We further define the possible adjuncts of C(X) (denoted by poss KB (C(X)) as all simple class expressions D for which C(D) is satisfiable w.r.t. KB . Moreover, we define the necessary adjuncts of C(X) (denoted by nec KB (C(X)) as the set of all simple class expressions D for which C(¬D) is unsatisfiable w.r.t. KB . Example 1.

Example 2 .

 2 Considering the knowledge base KB introduced above, the pointed class expression EUCitizen ⊔ ∃livesIn.(EUCountry ⊔ ∃colonyOf.X) would allow for the class EUCountry as possible adjunct, as the class EUCitizen ⊔ ∃livesIn.(EUCountry ⊔ ∃colonyOf.EUCountry) is still satisfiable thanks to either of the disjuncts EUCitizen and EUCountry.

Definition 3 .Example 3 .

 33 The pruning of a pointed CI class expression is obtained by applying the recursive function prune (we tacitly exploit commutativity of ⊓ and ⊔ to reduce cases):prune(X) := X prune(C(X) ⊓ D) := prune(C(X)) ⊓ D prune(C(X) ⊔ D) := prune(C(X))prune(∃r.C(X)) := ∃r.prune(C(X)) prune(∃r -.C(X)) := ∃r -.prune(C(X)) Continuing the above example, we obtain prune(EUCitizen ⊔ ∃livesIn.(EUCountry ⊔ ∃colonyOf.X))= ∃livesIn.∃colonyOf.X.Definition 4. Let KB be a knowledge base and let C be a CI class expression in which a union D 1 ⊔ D 2 occurs as a subexpression. Let C ′ (X) be obtained from C by replacing this occurrence with X, such that

Proposition 2 .Example 5 .

 25 For any not fully balanced CI class expression C there is a CI class expression C ′ such that-C ′ is fully balanced, -KB |= C ≡ C ′ -C ′ isobtained by the repeated replacement of imbalanced occurrences of unions by the respective non-fake disjunct. Given KB from above, we find that the (not fully balanced) class expression EUCitizen ⊔ ∃livesIn.(EUCountry ⊔ ∃colonyOf.EUCountry) and the fully balanced class expression EUCitizen ⊔ ∃livesIn.(EUCountry) are equivalent w.r.t. KB .

Definition 5 .Example 6 .

 56 Given a knowledge base KB and a pointed CI class expression C(X), we define the nice possible adjuncts of C(X) (denoted by poss KB (C(X)) as all simple class expressions D for which C(D) is fully balanced w.r.t. KB . Considering the knowledge base from above, we obtain EUCountry ∈ poss KB (EUCitizen ⊔ ∃livesIn.(EUCountry ⊔ ∃colonyOf.X)) since inserting EUCountry for X would result in a not fully balanced class.

Fig. 1 .

 1 Fig. 1. Screenshot of the Possible World Explorer (PEW) showing that, according to the pizza ontology, a pizza can have no topping.

Fig. 2 .

 2 Fig. 2. A screenshot showing, among other things, that a country can be some food, and can have a country of origin.

Fig. 3 .

 3 Fig.3. A screenshot showing that a vegetarian pizza may contain some meat or fish.

Table 2 .

 2 Syntax and semantics of SROIQ axioms

	Axiom α	I |= α, if

  EUCitizen ⊔ ∃livesIn.(EUCountry ⊔ ∃colonyOf.EUCountry) can be found to be not fully balanced since it contains the imbalanced occurrence of EUCountry ⊔ ∃colonyOf.EUCountry with ∃colonyOf.EUCountry being the fake disjunct since prune(EUCitizen⊔∃livesIn.X)[∃colonyOf.EUCountry/X] = (∃livesIn.X)[∃colonyOf.EUCountry/X] = ∃livesIn.∃colonyOf.EUCountry) is unsatisfiable w.r.t. KB (see above).

are satisfiable w.r.t. KB . Otherwise, we say the occurrence is imbalanced and call every D i with unsatisfiable prune(C ′ (X))[D i /X] a fake disjunct.

A CI class expression C is called fully balanced if it is satisfiable and all occurrences of union subexpressions are balanced. A pointed class expression C(X) is called fully balanced if C(⊤) is fully balanced.

Example 4.

Note that, on this general level, the distinction is conceptual rather than technical: for instance, the positive constraint that all catholic priests must be unmarried can likewise be read as the negative constraint that the existence of a married catholic priest is impossible.

Note that RDF and RDFS, though certainly more widespread, do not allow for the specification of negative constraints. In fact, the only way to cause an inconsistency in RDFS -namely via XML-clashes -should be seen as a feature which was introduced accidentally rather than intentionally, cf.[START_REF] Hitzler | Foundations of Semantic Web Technologies[END_REF], Section 3.3.3.

Finiteness of the vocabulary is required for the further considerations. This does not impose a restriction since the vocabulary is not bounded and can be extended whenever this should be necessary.

We use the terms knowledge base and ontology interchangeably.

We assume the usual regularity assumption for SROIQ, but omit it for space reasons.

In fact, the navigation paradigm for building such class expression will be such that it even discourages the use of this simple form of negation.

We adopt the Semantic Web practice of flipping letters in acronyms.

http://owlapi.sourceforge.net/

http://www.irisa.fr/LIS/softwares/sewelis/

http://www.co-ode.org/ontologies/pizza/pizza.owl

Acknowledgements This work was performed in the course of a research visit of Sebastian Rudolph in Rennes supported by IRISA and University Rennes 1.


Sébastien Ferré
email: ferre@irisa.fr

SQUALL: a Controlled Natural Language for Querying and Updating RDF Graphs

Formal languages play a central role in the Semantic Web. An important aspect regarding their design is syntax as it plays a crucial role in the wide acceptance of the Semantic Web approach. The main advantage of controlled natural languages (CNL) is to reconcile the high-level and natural syntax of natural languages, and the precision and lack of ambiguity of formal languages. In the context of the Semantic Web and Linked Open Data, CNL could not only allow more people to contribute by abstracting from the low-level details, but also make experienced people more productive, and make the produced documents easier to share and maintain. We introduce SQUALL, a controlled natural language for querying and updating RDF graphs. It has a strong adequacy with RDF, an expressiveness close to SPARQL 1.1, and a CNL syntax that completely abstracts from low-level notions such as bindings and relational algebra. We formally define the syntax and semantics of SQUALL as a Montague grammar, and its translation to SPARQL. It features disjunction, negation, quantifiers, built-in predicates, aggregations with grouping, and n-ary relations through reification.

Introduction

The Semantic Web [1,[START_REF] Hitzler | Foundations of Semantic Web Technologies[END_REF] is founded on a number of formal languages, used to represent: data (RDF), ontologies (RDFS, OWL), rules (SWRL), queries and updates (SPARQL). In this paper, we focus on queries and updates. SPARQL is a very expressive query language [START_REF] Pérez | Semantics and complexity of SPARQL[END_REF] as it includes relational algebra, and recently included aggregates, subqueries, negation, and property paths (SPARQL 1.11 ). It has also been extended with an update language for RDF graphs (SPARQL 1.1 Update2 ). However, its usability is limited because it exhibits low-level notions from relational algebra (e.g., bindings, join, union), and logic (e.g., variables, connectors, quantifiers). An ideal candidate for combining expressiveness and usability is natural language. However, full natural languages have a weak adequacy to Semantic Web formalisms [START_REF] Haase | A comparison of RDF query languages[END_REF], because they are too expressive and too ambiguous. A number of NLP-based systems have been developped for querying the Semantic Web, e.g., Aqualog [START_REF] Lopez | Aqualog: An ontology-driven question answering system for organizational semantic intranets[END_REF], FREyA [START_REF] Damljanovic | Identification of the question focus: Combining syntactic analysis and ontology-based lookup through the user interaction[END_REF]. However, those systems are generally limited to simple questions (typically equivalent to SPARQL basic graph patterns), and cannot be used for updates. For instance, Aqualog queries are limited to two-triples patterns. Therefore, those systems are adequate for simple needs, but are in no way a substitute for formal languages like SPARQL.

Our objective is to define an expressive formal query and update language as a fragment of a natural language. Like Montague, we think that "There is no important theoretical difference between natural languages and the artificial languages of logicians" [START_REF] Montague | Universal grammar[END_REF]. This opinion is supported by the existence of Controlled Natural Languages (CNL) [START_REF] Smart | Controlled natural languages and the semantic web[END_REF][START_REF] Fuchs | Attempto Controlled English meets the challenges of knowledge representation, reasoning, interoperability and user interfaces[END_REF]. The main advantage of CNLs is to improve usability by reusing the cognitive capabilities of people, and therefore reducing their learning effort, while retaining the properties of formal languages. To the best of our knowledge, no existing CNL fulfills adequacy and interoperability with RDF and SPARQL. ACE [START_REF] Fuchs | Attempto Controlled English meets the challenges of knowledge representation, reasoning, interoperability and user interfaces[END_REF] is a general purpose CNL, and requires the definition of a lexicon, which is not available for most RDF datasets (e.g., Linked Open Data). SOS or Rabbit cover OWL ontologies, and also assume some lexical knowledge [START_REF] Schwitter | A comparison of three controlled natural languages for OWL 1.1[END_REF].

In this paper, we introduce SQUALL, a Semantic Query and Update High-Level Language. It qualifies as a CNL for querying and updating RDF graphs. Its contribution is not about expressiveness, which is close to SPARQL. The contribution of SQUALL is to combine (1) an expressiveness close to SPARQL 1.1, (2) a high-level and natural syntax that completely abstracts from low-level notions such as bindings or relational algebra, and (3) a full adequacy with Semantic Web formalisms. SQUALL shares the motivation for a nicer syntax with RDF notations like Turtle and N3, but is rich enough to be a standalone language. The focus of this paper is on the syntax, retaining existing SPARQL notations at the lexical level, i.e., for non-grammatical words (URIs, literals, and variables). This makes SQUALL fully and directly interoperable with existing notations, and this removes all ambiguity at the lexical level. The drawback is that SQUALL sentences may look unnatural because URIs are invariant with respect to number or person: e.g., URI ":Person" stands for "person" and "people", URI ":knows" stands for "knows", "know". Whenever a lexicon, i.e. a non-ambiguous mapping from natural words to URIs and literals, is available or can be produced automatically from an ontology [START_REF] Lopez | Aqualog: An ontology-driven question answering system for organizational semantic intranets[END_REF], it can easily be integrated into SQUALL to make sentences more natural. In any way, SQUALL has to be learned, like any other formal language. However, we think that it is easier to learn, and that it makes it easier to formulate complex queries and updates: e.g., "for which researcher-s ?X, in graph DBLP every publication whose author is ?X and whose year ≥ 2000 has at least 2 author-s ?" is a valid query in SQUALL.

In Section 2, we first give preliminaries about the Semantic Web and Montague grammars. In Section 3, we formally define the syntax and semantics of SQUALL, where semantics is given in terms of an intermediate logical language. Section 4 provides a translation from this intermediate language to SPARQL, therefore providing a concrete semantics as well as a possible implementation of SQUALL as a query and update interface. Section 5 presents our implementa-tion, and illustrates SQUALL and its translation to SPARQL with the above complex query. Section 6 concludes this paper.

Preliminaries

We recall basic facts about the Semantic Web and Montague grammars. The Semantic Web provides, through RDF, the data model underlying both SPARQL and SQUALL. Montague grammars provide the theoretical framework in which we formally define the syntax and semantics of SQUALL.

Semantic Web

The Semantic Web (SW) is founded on several representation languages, such as RDF, RDFS, and OWL, which provide increasing inference capabilities [START_REF] Hitzler | Foundations of Semantic Web Technologies[END_REF]. The two basic units of these languages are resources and triples. A resource can be either a URI (Uniform Resource Identifier), a literal (e.g., a string, a number, a date), or a blank node, i.e., an anonymous resource. A URI is the absolute name of a resource, i.e., an entity, and plays the same role as a URL w.r.t. web pages. Like URLs, a URI can be a long and cumbersome string (e.g., http://www.w3.org/1999/02/22-rdf-syntax-ns#type), so that it is often denoted by a qualified name (e.g., rdf:type), where rdf: is the RDF namespace. In the N3 notation, the default namespace : can be omitted for qualified names that do not collide with reserved keywords (bare qualified names).

A triple (s p o) is made of 3 resources, and can be read as a simple sentence, where s is the subject, p is the verb (called the predicate), and o is the object. For instance, the triple (Bob friend Alice) says that "Bob has a friend Alice", where Bob and Alice are the bare qualified names of two individuals, and friend is the bare qualified name of a property, i.e., a binary relation. The triple (Bob rdf:type man) says that "Bob has type man", or simply "Bob is a man". Here, the resource man is used as a class, and rdf:type is a property from the RDF namespace. The triple (man rdfs:subClassOf person) says that "man is a subclass of person", or simply "every man is a person". The set of all triples of a knowledge base forms an RDF graph.

Query languages provide on semantic web knowledge bases the same service as SQL on relational databases. They generally assume that implicit triples have been inferred and added to the base. The most well-known query language, SPARQL, reuses the SELECT FROM WHERE shape of SQL queries, using graph patterns in the WHERE clause. A graph pattern G is one of:

a triple pattern (s p o .) made of RDF terms and variables (e.g., ?x), -a conjunction of two patterns ({G 1 G 2 }), -an union of two patterns (G 1 UNION G 2 ), -an optional pattern (OPTIONAL G 1 ), -a filter pattern (FILTER C), where C is a constraint, i.e., either a Boolean expression based on primitive predicates (e.g., comparison, string matching), or a negated graph pattern (NOT EXISTS G 1 ),

a named graph pattern (GRAPH g G 1 ), where g is URI or a variable denoting a named graph, -a subquery.

Aggregation operators can be used in the SELECT clause (e.g., COUNT, SUM), and GROUP BY clauses can be added to a query. SPARQL has been extended into an update language to insert and delete triples in/from a graph. The most general update form is INSERT I DELETE D WHERE G, where I and D must be sets of triple patterns, and G is a graph pattern that defines bindings for variables occuring in I and D.

Montague Grammars

Montague grammars [START_REF] Dowty | Introduction to Montague Semantics[END_REF] are an approach to natural language semantics that is based on formal logic and λ-calculus. It is named after the American logician Richard Montague, who pioneered this approach [START_REF] Montague | Universal grammar[END_REF]. A Montague grammar is a context-free generative grammar, where each rule is decorated by a λ-term that denotes the semantics of the syntactic construct defined by the rule. For example, the following rule gives the syntax, semantics, and an example of globally existentially quantified sentences:

S → there is NP { np λx.true } "there is [NP a man]"
Here, there and is are keywords, or grammatical words, of the language; S (for sentence) and NP (for noun phrase) are syntagms. The semantics is given between curly brackets, and is defined in a fully compositional style, i.e., the semantics of a construct is always a composition of the semantics of sub-constructs. The semantics of a sub-construct is given by the lowercase name of the corresponding syntagm. Every λ-term is typed, and the type of the semantics of a given syntagm is always the same. By convention, we name λ-variables according to their type: x, y, z for RDF resources (a.k.a. Montague entities), p for RDF properties, t for reified statements (both are special kinds of resources), d for descriptions, and s for sentences. Sentences are the intention of truth values (a.k.a. Montague propositions), and descriptions are the intention of sets of resources (a.k.a. Montague properties), i.e., of functions from resources to sentences. In the above rule, x denotes a resource, true denotes a sentence, and np denotes the intention of a set of descriptions, i.e., a function from descriptions to sentences (a.k.a. Montague properties of properties). Therefore, the whole λ-term denotes a sentence. The constants used in those λ-terms are the constructors of the intermediate language (e.g., and, exists), and RDF terms. The λ-terms obtained by composition can be simplified according to λ-calculus, through β-reduction (e.g., (λx.s) y = β s[x ← y]), and η-expansion (e.g., d = η λx.(d x)).

Syntax and Semantics of SQUALL

In this section, we formally define the syntax and semantics of SQUALL in the style of Montague grammars. This provides a translation from the concrete and natural syntax of SQUALL to an intermediate logical language, rather than directly in terms of an existing query language for the Semantic Web. This is a common practice in the compilation of high-level programming languages, and has a number of advantages. First, it makes the semantics easier to write and understand because defined at a more abstract level. Second, it gives freedom in the choice of the implementation. For instance, the operational semantics of the intermediate language can be given by translating it to an existing language, e.g., SPARQL; by interpreting it in a relational algebra engine; or by using continuation passing-style, like in Prolog. In Section 4, we sketch a solution in the first approach.

We first define a core language corresponding to RDF triples as simple sentences. We then detail a number of orthogonal extensions: relational algebra, queries, quantifiers, reification and n-ary relations, built-in predicates, and aggregations with grouping. The Montague grammars given in this paper provide a self-contained specification of the syntax and semantics of SQUALL.

Lexical Conventions

The lexical conventions for RDF terms and variables are the same as in Turtle, N3 and SPARQL. In SQUALL examples, we assume the usual namespaces rdf:, rdfs:, and the default namespace for the domain vocabulary so that bare qualified names can be used for most classes and properties. For reasons of space in SQUALL examples, we will use capital letters (like A, B) instead of full URIs to denote individuals (e.g., publications, persons). The keywords of SQUALL are grammatical words of English: e.g., is, of, and, every.

In the scope of this paper, SQUALL directly uses URIs for non-grammatical words, and therefore makes no distinction between singular and plural, nor between nouns and verbs at the lexical level (it does however at the syntactic level). A more essential distinction, which is readily available in RDF schemas, is between unary predicates called classes, and binary predicates called properties. Therefore, RDF classes are used as nouns (e.g., woman) and intransitive verbs (e.g., work), while RDF properties are used as relation nouns (e.g., author) and transitive verbs (e.g, know). For a slightly improved presentation of SQUALL sentences, we allow grammatical suffixes to be appended to URIs: e.g., "work-s" for the third person singular, "author-s" for the plural.

Triples

A triple (s p o) can be seen as a sentence. The tradition in linguistics [2] is to analyse s and o as noun phrases (NP ), p o as a verb phrase (VP ), and the whole triple as a sentence (S). In a Semantic Web context, a NP can be a term (Term), i.e., one of a URI, a literal, or a variable. A unary predicate (P1 ) can be used as an intransitive verb, and a binary predicate (P2 ) can be used as a transitive verb followed by an object NP . In a Semantic Web context, a P1 is typically a class URI, and a P2 is typically a property URI. Variables can also be used as predicates.

S → NP VP { np vp } "[NP A] [VP know-s B]" NP → Term { λd.(d term) } "A" VP → P1 { λx.(p1 x) } "[P1 work-s]" | P2 NP { λx.(np λy.(p2 x y)) } "[P2 know-s] [NP B]" P1 → ClassURI { λx.(type x uri ) } "work" | Var { λx.(type x var ) } "?C" P2 → PropertyURI { λx.λy.(stat x uri y) } "know" | Var { λx.λy.(stat x var y) } "?P"
In the semantics, (stat x p y) denotes a triple statement x p y, and (type x c) is a shorthand for (stat x rdf:type c). We also define (thing x) as a shorthand for (type x rdfs:Resource). The semantics of a term, when used as a NP , is the set of descriptions (λd) of which the term is an instance (d term).

The semantics of a verb phrase (P2 NP ) is the description of resources x such that the description of the resources y that are connected to x through the property p2 (p2 x y), is an instance of np. For instance, the sentence This complexity makes sense when introducing determiners and quantifiers (see Section 3.6).

"A know-s B" is parsed as "[S [NP A] [VP [P2 know-s] [NP B]]]",

Relational Algebra

For queries, SQUALL provides the algebraic operators of SPARQL [START_REF] Pérez | Semantics and complexity of SPARQL[END_REF]: and for joins, or for unions, not for differences and negations, maybe for optional patterns. Like in Turtle, the coordination and can be replaced by a dot (.) for sentences (S), and by a comma (,) for NP s.

∆ → not ∆ 1 { not δ 1 } "not [VP know-s B]" | ∆ 1 and ∆ 2 { and δ 1 δ 2 } "[VP work-s] and [VP cite-s X]" | ∆ 1 or ∆ 2 { or δ 1 δ 2 } "[NP A] or [NP B]" | maybe ∆ 1 { option δ 1 } "maybe [VP know-s B]"
In this rule, ∆ stands for any syntagm so that algebraic operators can coordinate all kinds of constructs: e.g., "A or B work-s and cite-s X", which is equivalent to "A work-s and cite-s X or B work-s and cite-s X". For a same constructor to apply in constructs having different types, it is necessary to add rewriting rules of λterms like the following: and δ 1 δ 2 α and (δ 1 α) (δ 2 α), where α stands for any argument: e.g., α is an entity

x if ∆ = VP , α is a description d if ∆ = NP .

Headed NPs, Relatives, and Auxiliary Verbs

This section augments the syntax to make it more natural and flexible. A NP can be made of a head preceded by a determiner (Det), and followed by an optional term as apposition (App), and a coordination of relatives (Rel ): e.g., "a woman ?A that is an author of X". The syntagms NG1 and NG2 (nominal groups) describe the possible heads, and the relative position of apposition and relatives (AR), which are both optional. Rel defines the possible relatives. Headed noun phrases allow for new verbal forms based on the auxiliary verbs is and has: e.g., "is a woman", "has an author". The syntagms NG1 , AR, Rel , AP denote descriptions, the syntagm NG2 denote binary predicates, while determiners denote binary relations between descriptions (i.e., quantifiers). "whose The meaning of the function init is clarified in Section 3.7 about reification. At this point, it can be assumed to be the identity function. The constructor exists is an existential quantification over an entity. The constructor eq represents equality (a binary predicate), and the constructor (bind x y) represents an assignement of x into y. The keywords the and where are propagated to the semantics using the constructors the and where, because their interpretation differs whether they occur in the scope of a query or an update (see Section 4).

NP → Det NG1 { λd.(det (init ng1 ) d) } "[Det a] [NG1 woman]" | Det NG2 of NP { λd.(np λx.(det (init (ng2 x)) d)) } "[Det the] [NG2 author-s] of [NP X]" Det → a(n) { λd 1 .
"[App?A] [ Rel that X cite-s]" | App { app } App → URI { λx.(eq x uri ) } "A" | Var { λx.(bind x var ) } "?X" | ǫ { λx.true } Rel → that VP { init vp } "that [VP know-s B]" | that NP P2 { init λx.
[P2 author] [VP is a woman]" VP → is/are AP { ap } "is [AP a woman]" | is/are Rel { rel } "is [ Rel such that ?A work-s]" | has/have Det P2 AR { λx.(det (p2 x) ar ) } "have [Det an] [P2 author] [ARthat X cite-s]" AP → Term { λx.(eq x term) } "A" | a(n)/the NG1 { ng1 } "a [NG1 woman]" | a(n)/the NG2 of NP { λx.(np λy.(ng2 y x)) } "the [NG2 author] of [NP X]" S →
In short, they are respectively equivalent to a and and in queries, and separate conditions and changes in updates.

Queries

Question words distinguish declarative sentences (updates) from interrogative sentences (queries): whether introduces a closed question, whose semantics encapsulates the sentence in the constructor ask; what can be used in place of any NP to form open questions. The constructor select applies to a description, and indicates that the instances of this description should be returned as query results. Multi-dimensional queries are expressed by using several occurences of what: e.g., "what is the author of what". Some question words are used as determiners. which has the same effect as what while allowing a restriction on returned resources: e.g., "which woman is an author of X". how many provides the easy expression of the most common aggregation, counting: e.g., "how many person is an author of X". The constructor count applies to a description, and indicates that the number of its instances should be returned as a query result.

S → whether S 1 { ask s 1 } "whether In order for the question constructors not to appear in the scope of non-question constructors, we introduce rewriting rules like the following: and (select λx.s 1 ) s 2 select λx.(and s 1 s 2 ); exists λx.(select λy.s) select λy.(exists λx.s). Similar rules are to be defined for count, other algebraic operators (like and) and other quantifiers (like exists), which are presented in Section 3.3 and 3.6. Also, we ensure that no select falls in the scope of count by adding the additional rewriting rule: count λx.(select λy.s) select λy.(count λx.s).

A sentence is a valid query if its semantics contains either one ask or any number of select and possibly one count. A sentence is a valid update if its semantics contains none of the question constructors. Otherwise, the sentence is invalid, and a syntax error should be returned.

Quantifiers

Quantifiers are commonplace in natural languages in the form of determiners, whereas they are notoriously difficult to express in SPARQL or SQL [START_REF] Hsu | Improving SQL with generalized quantifiers[END_REF]. The quantifier exists applies to a description, and checks that its extension is not empty. The quantifier forall applies to two descriptions, and checks that the extension of the first is included in the extension of the second. The constructor atleast i applies to a description, and checks that its extension has at least i elements. A possible use of them is: "every person is an author of at least 10 publication-s".

Det → some { λd 1 .λd 2 .(exists (and

d 1 d 2 )) } | every { λd 1 .λd 2 .(forall d 1 d 2 ) } | no { λd 1 .λd 2 .
(not (exists (and

d 1 d 2 ))) } | at least i { λd 1 .λd 2 .(atleast i (and d 1 d 2 )) } S → for NP , S { np λx.s } | there is NP { np λx.true }
The grammar rules are defined so that the scope of quantifiers are leftmostoutermost, and are restricted to the scope of the related verb. Therefore, "every man love-s some woman" means there is possibly a different woman for each man; while in "there is a woman that every man love-s" means there is a single woman. The keywords for and there is introduce global quantifiers, in a style closer to mathematical logic. Their scope extends to the end of the sentence, which may be a coordinated sentence: e.g., "for every publication ?X, ?X has an author ?A and ?A cite-s ?X". Relatives introduced by such that can be used in a global existential quantification: "there is a person ?X such that no publication has the author ?X".

Reification and N-ary Predicates

RDF triples can be reified as statements. Therefore, it is useful to allow statements about statements. The keyword that turns a sentence into a noun phrase, changing the focus from the truth of the sentence to the statements involved in the sentence. The variable t is used for denoting individual statements. Here it becomes necessary to explicit two arguments shared by all constructs, and that were left implicit so far (thanks to η-equivalence of λ-calculus): a is a list of additional arguments to the predicate of the sentence, and g denotes a graph, i.e., a set of statements. Together, they form the context in which a sentence is interpreted. Contexts are the counterpart of worlds in Montague semantics. The extension of a phrase is obtained by passing a context, and an intension is formed by abstracting over a context.

In the sentence "A say-s that B is an author of X", the object of the property "say" is the statement of the triple (X author B). In the semantics, the main clause (verb "say-s") abstracted over its object and receiving its own context (λt.(stat A say t a g)) denotes a graph (i.e., a set of statements), and is passed as a context to the dependent clause (stat X author B). This generalizes the GRAPH construct in SPARQL, where a graph would be restricted to the form λt.(stat t graph G), where the triple (t graph G) would mean that the statement t is a member of ("has graph") the named graph G (a URI or a variable).

The other rules define prepositions (Prep) and prepositional phrases (PP ), and their inclusion in sentences. A PP is introduced by at or in, and is followed by a Prep and a NP . It modifies a sentence by adding an argument to its context (constructor arg), or by encapsulating it in a graph (constructor graph). Each argument is a pair (uri , term), where uri defines the role of the argument w.r.t. the statement, much like "rdf:subject", "rdf:predicate", and "rdf:object"; and term is the argument itself. Those arguments provide means for expressing n-ary relationships. For example, "A is an author of X at rank 1" means that A is the first author of X; and "A sell-s X in year 2009 at amount 10" means that A sold 10 units of X in 2009.

The remaining rules say that prepositional phrases can occur anywhere in a sentence, and the syntagms OP (object phrase) and CP (complement phrase) are introduced to retain the leftmost-outermost scope rule for quantifiers. Therefore, the rigidity of this scope rule is balanced by the free ordering of PP s, the possible inversion between subject and object (of), and the global quantifiers introduced by for. An example of query that uses a number of those constructs is: "at which venue every professor that work-s at place X speak-s at some time". It is now possible to clarify and define the constructors init and arg that have already been used. The constructor init reinitializes the list of arguments in some construct: init = λd.λx.λa.(d x ()). This is useful to restrict the passing of arguments to the predicate of a sentence, and to avoid its propagation to noun groups and relatives for instance. The constructor arg adds an argument to the current list of arguments, waiting to be passed to the main predicate of the sentence: arg = λuri .λz.λs.λa.(s ((uri , z), a)). graph is a special preposition that represents the membership of statements to SPARQL named graphs.

In order to pass the context down to arguments of algebraic operators, quantifiers, and question constructors, it is necessary to define rewriting rules like the following: true a g true, and s 1 s 2 a g and (s 1 a g) (s 2 a g), exists d a g exists λx.(d x a g).

Built-in Predicates and Aggregations

Built-in predicates are used in SPARQL constraints (e.g., comparison, arithmetic, string matching), and expect a variable number of arguments. They can be used as nouns or intransitive verbs (Pred1URI ), when one argument plays the role of a subject, and as relation noun or transitive verbs (Pred2URI ), when two arguments play the role of subject and object. Additional arguments are represented through prepositional phrases, assigning a different preposition URI to each. For example, assuming the binary predicate "match" for regular expression matching, and the unary predicate "Monday" denoting the set of Monday dates, the following query can be expressed: "which woman has a lastname that match-es "Smi.*" and a birth whose date is a Monday".

The head of a noun phrase (NG1 ) can be an aggregator followed by the set of what should be aggregated, and optionally followed by a list of grouping dimensions introduced by per. Each dimension is an AP that specifies the set of possible values for this dimension: e.g., "what is the count of the publication-s ?P per the year of ?P, and the affiliation of an author of ?P". This construction produces bindings for the aggregated value and each dimension.

P1 → Pred1URI { λx.(pred1 uri x) }
"Monday" P2 → Pred2URI { λx.λy.(pred2 uri x y) } "match" NG1 → AggregURI of AP (per AP + i )? { λx.(aggreg uri x ap (ap i ) i ) } "count of [AP the publication ?P] per [AP the year of ?P]"

Handling of Ambiguity

The price for the natural and flexible syntax of SQUALL is ambiguity, i.e., the fact that some sentences can be parsed in different ways possibly leading to different semantics. In SQUALL, ambiguities are resolved by the following rules:

1. when forming a construct ∆ from one or two constructs of same syntagm ∆ (e.g., coordinating 2 NP s, modifying a sentence with a PP ), algebraic operators have priority (in decreasing priority order: not, maybe, and, or, where) over sentence modifiers (PP as a prefix, and global quantifiers for NP ). Punctuation has lowest priority, and right-associativity is used for binary coordinations; 2. smaller syntagms have priority over larger syntagms, i.e., in decreasing priority order: P1 , P2 , Det, Rel , NG1 , NG2 , AP , NP , PP , CP , OP , VP , S; 3. in case of ambiguity between forming two constructs of same syntagm, the shorter construct is chosen.

Round brackets can be used for every syntagms to escape those rules. Rule 2 implies that "a man or woman" is interpreted as "a (man or woman)" rather than "(a man) or woman", as NG1 has priority over NP . Rule 3 implies that in "A know-s a researcher that X cite-s at venue V ", the PP "at venue V " binds to the shorter VP "cite-s ..." rather than to the longer VP "know-s ...".

Translation to SPARQL

An operational semantics can be given to SQUALL by translating its intermediate language to SPARQL. Given a SQUALL sentence S with semantics s, the translation of S in the intermediate language is the formula f = s () g 0 , i.e., the sentence initialized with an empty list of arguments, and some default graph g 0 (e.g., λt.true). In order to simplify this formula, we remove some of the constructors of the intermediate language by giving them a definition. For example, the triple (x p y) passed to the constructor stat is reified by stating the existence of a statement resource t, which is connected to its subject, predicate, object, and arguments through roles. Each connection is represented using the new constructor triple that represents a non-reifiable triple. Those connections are completed by stating that the statement t belongs to the given graph g. This can be simplified into triple x p y when there are no argument, and the graph is λt.true. The constructor eq is defined by the built-in predicate =. The constructors atleast and count are defined in terms of the aggregator COUNT, and the built-in predicate ≥. The constructor fold is the classical iterator on lists.

A term (fold f e (x, x)) reduces to (fold f (f e x) x), and a term (fold f e ()) reduces to e. stat = λx.λp.λy.λa.λg.(exists λt.(fold λq.λ(uri , z).(and q (triple t uri z)) (g t) ((rdf:subject, x), (rdf:predicate, p), (rdf:object, y), a))) eq = λx.λy.(pred2 (=) x y) atleast = λi.λd.(exists λx.(and

(aggreg COUNT x d ()) (pred2 ≥ x i))) count = λd.(select λx.(aggreg COUNT x d ()))
After applying those definitions, the only remaining constructors are: triple, bind, pred1, pred2, aggreg, true, not, and, or, option, where, exists, forall, the, ask, select. We define in the following their translation to the queries and updates of SPARQL. Those translations are chosen to be concise, and not to be optimal in any way. The SPARQL translation of a formula f is denoted by [f ], and [X | f ] Q is an auxialiary translation for multi-dimensional queries. The two other auxiliary translations are [f ] G for producing graph patterns (that generate bindings), and [f ] U for producing updates (that insert and delete triples). An update is a triple (I, D, G), where I is a graph to be inserted, D is a graph to be deleted, and G is a graph pattern.

Compare the translation of where with graph patterns. In updates, it introduces a graph pattern, whereas in a graph pattern, it refines it like and. The same can be said for the quantifier the.

Implementation and Illustration

The contents of this paper has been implemented in less than 500 lines of OCaml 3 , a functional language. The code is very close to the formalism used in this paper, which makes it easy to extend the theory and the code in parallel. The source code, and a SPARQL translator Web form are available from the SQUALL web page at http://www.irisa.fr/LIS/softwares/squall.

As an illustration of the translation to SPARQL, we consider the sentence given in the introduction: "for which researcher-s ?X, in graph DBLP every publication whose author is ?X and whose year ≥ 2000 has at least 2 author-s". Its syntactic analysis is and its SPARQL translation is as follows (with some reformatting, and unreifying triples whose reification is not used):

SELECT ?

Conclusion

SQUALL is a Semantic Query and Update High-Level Language that provides a controlled natural language on top of SPARQL 1.1, while preserving adequacy, 3 http://caml.inria.fr/ocaml/ interoperability, and expressiveness. Its syntax and semantics are formally defined as a Montague grammar. The semantics of SQUALL sentences are formulated in a logical intermediate language. We have sketched a translation from this intermediate language to SPARQL, thus providing an operational semantics and a possible implementation for SQUALL. Possible future work include the addition of natural language constructs (e.g., arithmetic and string expressions, comparatives and superlatives, anaphoras other than variables), the full coverage of SPARQL 1.1 (e.g., expressions, property paths), and the use of ontologies and lexicons to improve the grammaticality of the language.

  and translates to (λd.(d A) λx.(λd.(d B) λy.(stat x know y))), which reduces to (stat A know B).

  (np λy.(p2 y x)) } "that [NP X] [P2 cite-s]" | such that S { init λx.s } "such that [S ?A work-s]" | Det NG2 of which VP { init λx.(det (ng2 x) vp) } "[Det an] [NG2 author] of which [VP know-s B]" | whose NG2 VP ≡ the NG2 of which VP "whose [NG2 author ?A] [VP cites-s a colleague of ?A]" | whose P2 is/are NP { λx.(np λy.(p2 x y)) }

  [S A know-s a woman]" NP → what ≡ which thing | whose NG2 ≡ the NG2 of what "whose [NG2 author ?A]" Det → which { λd 1 .λd 2 .(select (and d 1 d 2 )) } | how many { λd 1 .λd 2 .(count (and d 1 d 2 )) }

  NP → that S { λd.λa.λg.(s () λt.(d t a g)) } "that [S A know-s B]" PP → at/in Prep NP { λs.(np λz.(prep z s)) } "at place [NP the city Rennes]" | at/in Det Prep AR ≡ at Prep Det thing AR "at [Det some] venue [ARwhose place is Rennes]" S → PP S { pp s } VP → PP VP { λx.(pp (vp x)) } | P1 CP { λx.(cp (p1 x)) } | P2 OP { λx.(op (p2 x)) } | is/are AP CP { λx.(cp (ap x)) } | has/have Det P2 AR CP { λx.(det λy.(cp (p2 x y)) ar ) } OP → PP OP { λd.(pp (op d)) } | NP CP { λd.(np λy.(cp (d y))) } CP → PP CP { λs.(pp (cp s)) } | ǫ { λs.s } Rel → at/in which Prep AR S { init λx.(and (ar x) (prep x s)) } "in which graph [S A work-s]" Prep → graph { graph } | URI { arg uri }

  "[S for [NP [Det which] [NG1 [P1 researcher-s] [AR[App?X]]]], [S [PP in [Prepgraph] [NP DBLP]] [S [NP [Det every] [NG1 [P1 publication] [AR[ Rel [ Rel whose [NG2 [P2 author]] [VP is [AP ?X]]] and [ Rel whose [NG2 [P2 year]] [VP [P2 ≥] [NP 2000]]]]]]] [VP has [Det at least 2] [P2 author-s]]]]]",

  λd 2 .(exists (and d 1 d 2 )) } | the { λd 1 .λd 2 .(the d 1 d 2 ) } NG1 → thing AR { and thing ar } "thing [ARthat cite-s A]" | P1 AR { and p1 ar } "[P1 woman] [AR?A]" NG2 → P2 AR { λx.λy.(and (p2 x y) (ar y)) } "[P2 author] [AR?A]" AR → App Rel { and app rel }

http://www.w3.org/TR/sparql11-query/

http://www.w3.org/TR/sparql11-update/