Stefano Mizzaro
email: mizzaro@uniud.it

Josiane Mothe
email: josiane.mothe@irit.fr

Why do you Think this Query is Difficult? A User Study on Human Query Prediction

Keywords: Information retrieval, Query difficulty, difficulty understanding 1. QUERY DIFFICULTY PREDICTION

Predicting if a query will be difficult for a system is important to improve retrieval effectiveness by implementing specific processing. There have been several attempts to predict difficulty, both automatically and manually; but without high accuracy at a preretrieval stage. In this paper, we focus rather on understanding why a query is perceived by humans as difficult. We ran two separated but related experiments in which we asked humans to provide both a query difficulty prediction and reasons to explain their prediction. Results show that: (i) reasons can be categorized into 4 classes; (ii) reasons can be framed into closed questions to be answered on a Likert scale; and (iii) some reasons correlate in a coherent way with the human predicted numerical difficulty. On the basis of these results it is possible to derive hints to be provided to help users when formulating their queries and to avoid them to rely on their wrong perception of difficulty.

One of the outcomes of IR international evaluation campaigns is that system and query variability is high [START_REF] Harman | The NRRC reliable information access (RIA) workshop[END_REF]. However, while there is some variability, some queries are difficult or easy for all the participants. For example in TREC Web 2014, which uses the ClueWeb 2012 corpus, the average ERR@20 for topic 278 "What are the lyrics to the theme song for "Mister Rogers' Neighborhood"?" is 0.0048 while the best run for that topic got 0.0820; this is a difficult topic for all systems. On the opposite, for topic 298 "medical care and jehovah's witnesses", the average ERR@20 is 0.5887 and the median is 0.5790; this is an easy topic.

The Reliable Information Access (RIA) workshop [START_REF] Harman | The NRRC reliable information access (RIA) workshop[END_REF][START_REF] Harman | Overview of the reliable information access workshop[END_REF] has been the first large scale attempt to try to understand query (and system) variability and difficulty. The two main conclusions of the failure analysis were: systems were missing an aspect of the query, generally the same aspect for all the systems, and "if a system can realize the problem associated with a given topic, then for well over half the topics studied, current technology should be able to improve results significantly" [START_REF] Harman | Overview of the reliable information access workshop[END_REF]. When considering failure analysis, 10 classes of topics were identified manually, but no indications were given on how to automatically assign a topic to a category. Following these findings, there have been many attempts to automatically predict query difficulty. The purpose of a query difficulty predictor is to decide whether a system is able to properly answer the current query [START_REF] Carmel | Estimating the query difficulty for information retrieval[END_REF]. Different kinds of automatic predictors have been proposed in the literature both pre- [START_REF] Hauff | A survey of pre-retrieval query performance predictors[END_REF] and post-retrieval [START_REF] Shtok | Predicting query performance by query-drift estimation[END_REF], based on statistics only or considering some linguistic features [START_REF] Mothe | Linguistic features to predict query difficulty[END_REF]. Automatic predictors correlate with actual or observed system effectiveness, but the correlation is always weak, even if it is slightly higher when considering post-retrieval predictors than pre-retrieval ones (although post-retrieval predictors are less interesting, because more costly, than pre-retrieval) [START_REF] Hauff | A survey of pre-retrieval query performance predictors[END_REF][START_REF] Mothe | Linguistic features to predict query difficulty[END_REF][START_REF] Shtok | Predicting query performance by query-drift estimation[END_REF]. These results limit their practical use in real applications.

Another research direction is addressed by Hauff et al. who analyzed the relationship between predictions by non IR expert users and system effectiveness [START_REF] Hauff | A comparison of user and system query performance predictions[END_REF]. The authors considered various queries for a single topic or information need and measured the ability of users to judge the quality of query suggestions. They found that: (i) users are not good at predicting system failure; and (ii) the correlations between the users' prediction and both system effectiveness and automatic predictors are weak. We also had similar results when asking annotators to predict query difficulty, under several different experimental conditions, with different user groups, and both from the crowd and from participants in laboratory experiments.

In this paper, rather than focusing on query difficulty rating, we focus on reasons why users think a query is going to be easy or difficult for a search engine. We decided to consider users who are not necessarily IR experts since the latter know how systems work and may not be representative of a large variety of real search engine users. Therefore, when compared to RIA [START_REF] Harman | The NRRC reliable information access (RIA) workshop[END_REF][START_REF] Harman | Overview of the reliable information access workshop[END_REF], we ask to non experts to provide reasons that explain query difficulty (or ease). When compared to Hauff et al. [START_REF] Hauff | A comparison of user and system query performance predictions[END_REF], rather than just asking for ratings, we focus on explanations and comments on difficulty.

To know more on these reasons, we performed a user study made up of the two experiments described in the next two sections.

EXPERIMENT 1: ELICITING REASONS

The first experiment aimed at eliciting free text reasons why queries are perceived as difficult or easy by users.

Experimental Design

While we were interested mainly in the reasons why users think a query is going to be easy or difficult for a search engine, the task for human annotators was both to predict the difficulty a search engine may encounter to answer an information need and to explain the reasons of their prediction. Indeed, it is probably more natural for annotators to choose an explicit rating first and then to focus on providing the reasons for it. When asked to annotate the topic difficulty, the main question the annotators had to think of was: is the system going to succeed/fail when processing this query? Does the annotator think the system will retrieve relevant information (an easy query) or not (difficulty query)?

Annotators were provided with the query (TREC topic title); they had to decide the difficulty on, and to comment on the difficulty rating they chose, using the query only. Annotators were asked to use a three level numeric scale: 1 for easy query, 2 for medium query, and 3 for difficult queries. They also could use 0 when they did not know, although they were encouraged to decide on the difficulty. In addition to grading the query difficulty, annotators were asked to indicate the reasons why they thought the query was easy/difficult. For a query and whatever the grade they gave, they could indicate both comments, on its difficult and easy natures. We did not provide any guidance to write the comments apart from using the keyword "Easy:" or "Difficult:" before any comment they write. The tool we provided does not allow them to go back to an annotation they had done previously.

The group of annotators was composed of 38 Master's Students (25 1st and 13 2nd year) in library and teaching studies; although they had been trained to use specialized search engines, they had just an introduction class on how search engines work. Annotators could choose as many topics they wanted from a set of 150 TREC topics. Topics were displayed in different order to avoid any bias, as the first topics may be treated differently because the task was new for annotators. Moreover, annotators could skip some topics if they wish; this was done to avoid them to work on a topic they did not understand or felt uncomfortable with. Since the annotation process is difficult, we tried to provide to the annotators the most favorable conditions. The drawback is that the number of annotations varies over topics; this makes numerical analyses more difficult (for example, when computing an average difficulty score the averages are computed over different numbers of scores) but we were here more interested in the reasons, and this kind of qualitative data is less prone to such difficulties.

In this experiment, we used TREC 6, 7, and 8 adhoc task topics.Although these collections are old, we think that the elicitation of reasons will not differ much with other collections. Of course, the annotators knew that the document collection is composed of newspaper articles from the 90s even though it may be difficult for an annotator nowadays to get a picture of what were the popular topics in newspapers more than twenty years ago.

Results and Analysis

We analyzed the comments that the annotators associated with the evaluation of difficulty. The objectives were (i) to see if there were some recurrent patterns, and (ii) to extract some trends in the

Descriptive Statistics

Figure 1 shows the number of queries as a function of the number of times it has been annotated by any of the 38 annotators. For example, 22 queries have been annotated a single time (left part of the figure); the most annotated query has been annotated 25 times (right side of the figure). In total 107 queries have been annotated at least by one annotator and 65 three times or more. Table 1 shows the distribution of grades, i.e., the number of times a given grade has been used (e.g., grade Easy has been used 227 times whatever the annotator and the query are).

We collected 460 annotations in total (one annotation count for one topic, one annotator). 107 topics have been graded by at least one annotator; a little fewer have been commented (6 topics have no comment associated with them). It is of course possible that other comments might be generated for the other topics, but with around 70% of the topics being annotated we can be rather confident that most of the reasons have been elicited in this experiment.

Recoding the Free Text Comments

We recoded the free text comments. Table 2 shows some examples of recoding that was made. Each comment could be recoded into more than one recoded phrases; for example the comment "terms are too general, there will be many documents retrieved" has been recoded into Too-General-Words and Many-Documents. We found out that there were mostly four types of comments, as shown in the table: T (on the topic itself), Q (on the query), W (on the words used), and D (on the documents or on the collection, e.g., if the annotator thinks that some document exists in the collection).

The table also shows how many comments were recoded in each category; however, notice that recoding is always subjective and another recoder may have recoded differently, thus these numbers just provide trends. In a few cases (about 5%), the comment was not explicitly associated with one of these classes. This was for example the case when annotators wrote vague without detailing if it was a query term which they found vague or the topic itself. A concrete example is the one of Query 417 (Title: creativity) for which the 5 annotators considered the query as difficult using comments such as "too broad, not enough targeted", "far too vague", "Risk of getting too many results" Too-Many-Documents "There are many documents on this" Many-Documents "far too vague topic", "keyword used very broad, risk of noise", and "a single search term, risk of getting too many results". While the last comments are directed to one or the other class, the first two are not. We notice that the four categories are roughly equally distributed and have a good coverage.

After recoding, we got 740 annotations for 572 graded queries (each query could be annotated by various annotators; in addition several recoded phrases can be associated with a single comment). For recoding we used 105 different recoding phrases (4 of which are not associated with any of the four categories).

Comments Associated with Ease and Difficulty

Table 3 shows the most frequent recoded phrases associated with ease (left part) and difficulty (right part). Remember that a given query can be annotated by some comments associated with both. For example, while Precise-Topic is generally associated with ease (66 times), it is also associated with difficulty in 3 cases. In that case it is associated with other comments, e.g. "The topic is very precise but it may be too specific". In the same way, Many-Documents is mostly associated with ease and Too-Many-Documents to difficulty, although Many-Documents is also associated with difficulty (users may have in mind either a recall-oriented or a precisionoriented task). Also, when Many-Documents is used associated with difficulty, it is generally associated with Risk-Of-Noise.

Annotator Effect

It may be that some annotators are more likely to use some types of comments than others, either because of what they think about how systems work or because of their search experiences.

We analyzed the link between annotators and the four categories of comments, i.e., associated with Word (W), Query (Q), Topic (T), and Document (D). We grouped the recoded phrases belonging to each category and built a matrix that associates annotators and the four categories of comments associated with. We then used Correspondence Analysis (CA) [START_REF] Benzécri | Correspondence analysis handbook[END_REF] on that matrix to visualize in one shot the relationships. CA is close to Principal Component Analysis (PCA) in its principle and appropriate when analyzing categorical variables which is the case here. Compared to PCA, CA allows to display in the same space the variables and observations (rows and columns). The distance between objects of any kind is meaningful.

Figure 2 shows the two first axes of the corresponding CA. The horizontal axis divides the figure into two parts. The top part is more related to comments on W and T and so are the annotators in this part of the figure. The bottom part is related to Q and D categories; so are the annotators displayed in this part of the figure. Moreover, the bottom left corner of the figure is more related to comments on D, as the annotators who are in the same corner while the bottom right part is more associated with comments on Q. The annotators near the origin of the axes use annotations from all four categories, while the annotators in the top right corner are more inclined to use comments on Q (according to the horizontal axis) and on W (vertical axis), but do not use comments on D. We went a step further to check if some annotators use some comments more than others by using the comments rather than the category of comments and found that it is indeed the case too.

EXPERIMENT 2: TESTING REASONS

The experiment described in the previous section allowed us to elicit reasons. However, free text questions have two drawbacks: first they need to be recoded and recoding is subjective, and second, annotators are sensitive to different features as we have shown in section 2.2.4. Based on these results, we decided to consider, rather than free text, closed and mandatory questions for the annotators to answer. Closed so that recoding will not be needed anymore, and mandatory so that the annotator effect will be less important. This is done in the second experiment, described in this section.

From Categories to Questions

We considered each of the 105 recoding phrases obtained in the previous experiment and transformed them into 32 closed questions (denoted with Qi in the following) that could be answered following a Likert scale. Examples of such questions are shown in the first column of Table 4. When recoding, we had tried to keep as most as possible the nuances annotators expressed. When rephrasing into questions, we removed these nuances to limit the number of questions and to remove some redundancy (e.g., precise, specific, focused, delimited, and clear were merged together).

Experimental Design

We performed a laboratory user study with 22 new volunteers mainly from our research institutes. They were recruited using generic emailing lists and they got a coupon for participating. Each of them was asked to annotate 10 queries (provided in a random order). We used 25 topics from TREC Web 2014 that uses ClueWeb 2012 corpus: we picked up the easiest 10, the most difficult 10, and the medium 5 according to the topic difficulty order presented in the overview paper [START_REF] Collins-Thompson | TREC 2014 Web Track Overview[END_REF]. We changed from TREC 6, 7, 8 to ClueWeb queries since the latter are more recent, might reflect more the types of current queries on the web, and are now more used in the IR community. Also, in the previous experiment some topics were not annotated: clearly the young students were not at ease with (some of the) old topics.

In order to make the statistical analysis more smooth and sound we collected the same number of predictions for each query; we thus consider the same number of annotators for each topic. Annotators had to annotate the level of difficulty of the query, but rather than asking them to provide the reason of their grading in free text only, we asked to answer the 32 predefined questions Qi using a five level scale, from -2 "I strongly disagree" to +2 "I strongly agree". With 32 Qi by 25 topics by 8 annotators each, we collected a total of 6400 reason ratings. The free text reasons they provided has not been analyzed yet.

Results

Table 4 shows on the second column the Pearson's correlation between the questions and the human prediction of difficulty. Only the 13 Qi having a statistically significant correlation (p-value < 0.05) are included. The seven Qi having values labeled with a * (Q13, Q17, Q18, Q19, Q23, Q24, Q26) have a correlation higher than 0.60 with a p-value < 0.005. These 13, and especially 7, Qi represent the reasons that, according to the users, correlate most with query difficulty. For example, users think a query is difficult because the topic has many aspects (Q13).

However, none of these 13 reasons that users think correlated with query difficulty, turns out to correlate with actual difficulty, with just one exception (Q26). This is shown in the third column in the table that reports the correlation with observed difficulty based on system effectiveness. We used the average ERR@20 as system effectiveness measure, calculated considering all the participant runs. Moreover, the correlation between the human prediction and actual difficulty is low (0.238, p-value 0.25), indeed a much lower value (and not statistically significant as well) than the correlation between Q26 and actual effectiveness, which is 0.45, p-value < 0.05. This means that to obtain a prediction of difficulty, it is much better to ask Q26 than to directly ask for a difficulty rating.

There is also the possibility that some Qi can be combined, maybe also with the difficulty prediction rating, and/or with automatic predictors, to obtain a more accurate numerical prediction. We do not have space here to present those results, but we note (see Figure 3) that some of the seven questions are redundant, and therefore there is no need to require the user to answer all of them.

DISCUSSION AND CONCLUSIONS

Other studies have shown that humans are bad query difficulty predictors [START_REF] Hauff | A comparison of user and system query performance predictions[END_REF] and generally think queries are easier for systems than they actually are. This paper is a first contribution to try to understand why users (rather than IR experts) think a query is easy or difficult for a search engine. In a first user study, reasons were elicited from free text comments on query difficulty. After a manual recoding and a deep analysis, we found a set of 105 reasons classified into four categories. We then framed 32 closed questions that cover all the mentioned reasons and can be answered through a Likert scale. We used those 32 questions in a second user study, and showed that thirteen correlate with the human prediction of difficulty, and seven of them highly. On the other hand, these questions do not correlate with observed system difficulty. These questions can thus be seen as explanation why humans wrongly think queries are easy or difficult. These results can be useful when training search engine users [START_REF] Efthimiadis | Teaching and learning in information retrieval[END_REF], e.g., to help them to formulate queries and to provide them with hints about their wrong perception of system effectiveness. For example, a user can be told (by a teacher or a search engine) that the fact the query seems usual or common is not linked to system effectiveness.

Figure 1 :

 1 Figure 1: Number of queries by annotation frequency

Figure 2 :

 2 Figure 2: CA, first components: annotators (triangles) and comment categories (ellipses).

Figure 3 :

 3 Figure 3: Pearson correlations between questions. Q18, Q19, Q23, and Q24 have a high correlation; they are redundant.

Table 1 :

 1 Distribution of grades used by annotators

	Grade:	Easy Medium Difficult Don't know
	Frequency:	227	188	140	17
	comments associated with classes of query difficulty as perceived
	by users/annotators.

Table 2 :

 2 Examples of recoding, grouped into four categories.

	Free text comment	Recoded phrase
	T: Topic (274 comments, 35 recoded phrases)
	"The topic is precise"	Precise-Topic
	Q: Query (142 comments, 23 recoded phrases)
	"The query is formulated in a clear way" Clear-Query
	"The query is not precise at all"	Broad-Query
	W: Words (180 comments, 28 recoded phrases)
	"A single word in the query"	1-Word
	"The term 'exploration' is polysemous" Polysemous-Word
	D: Documents (143 comments, 15 recoded phrases)

Table 3 :

 3 Most frequent comments.

	Easy because		Difficult because
	Precise-Topic	66	Risk-Of-Noise	50
	Many-Documents	45	Broad-Topic	43
	No-Polysemous-Word 31	Missing-Context	34
	Precise-Words	25	Polysemous-Words 22
	Clear-Query	19	Several-Aspects	20
	Usual-Topic	16	Missing-Where	16

Table 4 :

 4 Examples of questions (column 1) with their Pearson's correlations with human predicted difficulty (col. 2) and actual difficulty (col. 3). Bold indicates a p-value < 0.05, * <0.005.

	Question	Correl.
	Q1: The query contains vague word(s)	.52 -.30
	Q3: The query contains word(s) relevant to the topic/query	-.41 .43
	Q10: The topic is unusual/uncommon/unknown	.52 .26
	Q13: The topic has several/many aspects	.61* -.07
	Q17: The topic is usual/common/known	.62* -.25
	Q18: The number of documents on the topic in the web is high -.69* -.34
	Q19: None or very few relevant documents will be retrieved	.88* .32
	Q20: Only relevant documents will be retrieved	-.47 .09
	Q23: Many of the relevant documents will be retrieved	-.86* -.20
	Q24: Many relevant documents will be retrieved	-.87* -.21
	Q26: The number of query words is too high	.62* .45
	Q28: The query contains various aspects	.46 -.12
	Q30: The query is clear	-.53 .30


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

Navigating the Semantic Web with Logical Information Systems

Keywords: semantic web, information retrieval, navigation, logical information system web sémantique, recherche d'information, navigation, systèmes d'information logiques

Exploratory search is about browsing and understanding an information base. It requires a more interactive process than retrieval search, where the user sends a query and the system returns answers. Logical Information Systems (LIS) support exploratory search by guiding users in the construction of queries, and by giving summaries of query results. The contribution of this paper is to adapt and extend LIS to the Semantic Web. We define a summarization and navigation data structure that provides rich views over data, and guides users from view to view. This guiding is proved consistent (i.e., never leads to an empty result set), and complete (i.e., every query can be reached by navigation only). The query language covers a large fragment of SPARQL, and is more concise by using a syntax close to description logics. Our approach could be implemented on top of existing tools for storing, reasoning and querying.

Introduction

With the growing amount of available ressources in the Semantic Web, it is a key issue to provide an easy and effective access to data and knowledge, not only to the specialist, but also to the casual user. The challenge is not only to allow users to retrieve particular ressources (e.g., flights), but to support them in the exploration of a domain knowledge (e.g., which are the destinations? which are the most frequent? with which companies and at which price?). We call the first mode retrieval search, and the second mode exploratory search [START_REF] Marchionini | Exploratory search: from finding to understanding[END_REF][START_REF] Sacco | Dynamic taxonomies and faceted search[END_REF].

We claim that most existing querying languages for the Semantic Web (e.g., SPARQL [START_REF] Pérez | Semantics and complexity of sparql[END_REF], SPARQL-DL [START_REF] Sirin | SPARQL-DL: SPARQL query for OWL-DL[END_REF], OWL-QL [START_REF] Fikes | OWL-QL -a language for deductive query answering on the semantic web[END_REF]), while expressive, are difficult to use, even for specialists, and do not provide enough feedback to satisfy exploratory search. Even if a user has a perfect knowledge of the syntax and semantics of the query language, she may be ignorant about the application vocabulary. Therefore, the class and property names she would use would certainly be undefined. A first approach is to use a semantic distance [START_REF] Corby | Querying the semantic web with corese search engine[END_REF] between classes and properties in order to match the query to ressources. The problem with any distance is that it makes hidden assumptions on the user intent. A second approach is to use a query assistant (e.g., Protégé) that suggests relevant classes and properties given a detailed modelling (e.g., domain and range of properties). In fact, this modelling is neither sufficient, nor entirely necessary. It is not sufficient because a query that is syntactically correct and semantically consistent w.r.t. the model can still produce no result (e.g., there might be a flight from Rennes to Washington, but it happens there is none). Some part of the modelling may be useful for inference purposes, but we show in this paper that it is not necessary for guiding users in the composition of useful queries.

Logical Information Systems (LIS) [START_REF] Ferré | An introduction to logical information systems[END_REF] have been introduced to solve the dilemma between an expressive querying language that is difficult to use (e.g., Boolean queries), and an intuitive but rigid navigation structure (e.g., file hierarchies). The solution retains the use of an expressive query language, but frees users from directly composing and modifying queries. Instead, a navigation process takes place, where the system provides suggestions to modify the query (navigation links), and the user makes choices. This navigation process has the following properties: (1) the user has full control on the search, and can make choices in any order, (2) the system makes no assumption on the user intents, (3) every information can be accessed through every possible path, (4) the user is guaranteed never to get an empty result (no dead-end). At each step of the navigation, the set of suggestions is organized as a summary of the current selection that provides insight and feedback on data, and thus supports exploratory search. LIS have been applied to real applications such as photo management [START_REF] Ferré | Camelis: a logical information system to organize and browse a collection of documents[END_REF], and geographical information systems [START_REF] Bedel | GEOLIS: A logical information system for geographical data[END_REF].

The contribution of this paper is to adapt and extend the LIS approach to the Semantic Web. LIS initially apply to a small subset of RDFS (rdf:type and rdfs:subClassOf are the only properties). A first extension to the Semantic Web has been proposed [START_REF] Allard | Dynamic taxonomies for the semantic web[END_REF], but with a query language restricted to the language of the basic description logic ALC. We here propose a navigation process that is (1) based on a query language whose expressivity is similar to SPARQL, and (2) as natural as the notation N3, and that is (3) consistent (no dead-end) and (4) complete (every query can be reached by navigation). Our approach builds upon and is compatible with existing techniques for designing and storing ontologies, reasoning, as well as querying languages and their implementations. In fact, the LIS approach should be seen as a layer on top of querying mechanisms, rather than an alternative to it.

We first give a short introduction of the principles of LIS in Section 2, before detailing in Section 3 how these principles are applied to the Semantic Web. We introduce a new query language with a DL-based syntax, and SPARQL-based semantics. Its expressivity is discussed in Section 4. A few perspectives are discussed in Section 4 before concluding.

Logical Information Systems

Logical Information Systems (LIS) [START_REF] Ferré | An introduction to logical information systems[END_REF][START_REF] Ferré | Camelis: a logical information system to organize and browse a collection of documents[END_REF] follows the logic-based approach to information retrieval [vR86]. A dataset is a set of objects, each object being described by a logical formula. On top of this, Formal Concept Analysis (FCA) [START_REF] Ganter | Formal Concept Analysis -Mathematical Foundations[END_REF], and more specifically its logical generalization [START_REF] Ferré | An introduction to logical information systems[END_REF], brings the rationale for tightly combining querying, navigation, and annotation. FCA defines a data structure, the concept lattice, that is automatically derived from the dataset, and is used for information retrieval, data analysis, and data mining. LIS use it as a summarization and navigation structure. Every change in the dataset automatically entails the update of the concept lattice, and hence of the summarization and navigation structure.

The LIS user interface is a local view of the concept lattice centered on a concept, the focus. The local view is made of three parts: (1) the query, (2) the extension, and (3) the index. The query is a logical formula. The extension is the set of objects that are matched by the query, along the logic-based approach [vR86]. The extension identifies the focus concept. Finally, the index is a finite subset of the logic that is restricted to formulas that match at least one object in the extension. The index plays the role of a summary or inventory of the extension, showing which kinds of objects there are, and how many of each kind there are. Figure 1 shows a screenshot of a LIS interface, where objects are photos, and formulas are about date, location, event, persons, etc. The query can be modified in three ways. To query by formula is to directly edit the query, which requires expertise or luck from the user. To navigate is to select formulas in the index in order to make the query more specific or more general. To query by examples is to select a set of objects in the extension, which leads to the query that is the conjunction of all common properties of the selected objects. In the three cases, the modification of the query entails the update of the extension, hence of the focus concept and the index. By definition of the index, no navigation link (a selection in the index) can lead to an empty result. Conversely, because the navigation structure is a lattice rather than a hierarchy, all valid conjunctions of formulas can be reached by navigation, and in any order. Contrary to querying by formula, navigation only requires from the user to recognize the meaning of formulas in the index, in the context of the application.

There exist several implementations of LIS1 . Camelis [START_REF] Ferré | Camelis: a logical information system to organize and browse a collection of documents[END_REF] (see Figure 1) is the most accessible to end-users with a dedicated graphical interface, and modules to extract metadata from photos, MP3 files, etc. It has been applied to the management of all sorts of files such as photos, music files, Java libraries, BibT E X files. LISFS [START_REF] Padioleau | A logic file system[END_REF] is a Linux file system, whose API is redefined along LIS principles. GEOLIS [START_REF] Bedel | GEOLIS: A logical information system for geographical data[END_REF] is a geographical information system based on LISFS. It has a web interface similar to the Camelis' interface except the extension is rendered on a map.

Navigating the Semantic Web

The contribution of this paper is to adapt the LIS framework to the Semantic Web. We consider the dataset to be an RDF graph [START_REF] Pérez | Semantics and complexity of sparql[END_REF], which may include both explicit and implicit facts (i.e., triples) through reasoning. In this paper, we do not make the distinction between the two. In practice, the implicit facts may be materialized in a preprocessing stage, or infered on demand. Inference rules can be OWL axioms, or SWRL rules. We assume pairwise disjoint infinite sets of IRIs (I), blank nodes (B), and literals (L). We call resources the set R = I ∪ B ∪ L resulting from the union of IRIs, blank nodes, and literals (indeed, RDFS defines rdfs:Literal as a sublcass of rdfs:Resource).

Definition 1 (RDF graph) An RDF graph is defined as a set of triples (s, p, o) ∈ (I ∪ B) × I × (I ∪ B ∪ L), where s is the subject, p is the predicate, and o is the object.

For illustration purposes, we consider RDF graphs about genealogical data. The IRIs of this domain are associated to a namespace gen:. This prefix is omitted if there is no ambiguity. Resources can be persons, events, places or literals such as names or dates. Persons belong to the class of men or women, may have a firstname, a lastname, a sex, a father, a mother, a spouse, and a birth. A birth is an event that may have a date and a place. Places can be described as parts of larger places. The use of OWL axioms may help to enforce some invariants, e.g., the spouse property is symmetrical, the father property is functional, and the part property is transitive.

In Section 3.1, we first redefine the LIS notion of local view. This comprises the definition of queries, the extension of queries, and the summarization index over extensions. Then, navigation links are defined in Section 3.2 on top of the local view. They allow users to navigate between different local views in a flexible way, and without having to type anything. A set of navigation links that has a practical size is proved consistent and complete. Figure 2 shows the user interface of our prototype, applied to the genealogy of George Washington (see http://www.irisa.fr/LIS/ferre/camelis/camelis2.html). It reflects the structure of a local view with the query at the top, the extension at the right, and the index at the left. This paper does not focus on interfaces, and this prototype has experimentation and illustration purposes for our navigation model.

Local View

Queries and Extensions

In LIS, the query defines the focus of the local view. For instance, a local view may put the focus on "women whose some parent was born in Virginia in 1642". This focus can be defined by the SPARQL query below. SPARQL is a W3C recommendation for querying RDF datasets. It is based on graph patterns that are matched over RDF graphs.

SELECT ?x WHERE { ?x rdf:type gen:woman .

?x gen:parent ?p . ?p gen:birth ?b . ?b gen:date 1642 . ?b gen:place ?l . gen:VA gen:part ?l}

A LIS query must necessarily define a set of resources, i.e., a mono-dimensional relation. This implies that we only need SPARQL queries with a single variable in the SELECT clause. This also means our queries are analogous to OWL complex classes (a.k.a. concept descriptions in Description Logics [BCM + 03]). In fact, the above query can be expressed in the description logic SHOIN that is behind OWL-DL:

Woman ∃parent.∃birth.(∃date.{1642} ∃place.∃partOf .{FRANCE }).
The property partOf is the inverse of part. The advantages of the DL syntax is that it is much more concise, and avoids the use of variables. LIS do not require from end-users the ability to write queries, but they do require from them to understand queries. Furthermore, we do not expect end-users to have education in computer science, and ideally, the queries should be understandable with little, if any, learning. We think the DL syntax is closer to this objective than the SPARQL syntax. At the same time, SPARQL has more expressive patterns (e.g., cycles), and a semantics that is less demanding w.r.t. logical inference.

We propose a new language for querying RDF graphs, where query results are restricted to sets of resources. Therefore, the expressions of this language are called complex classes. It also makes use of complex properties, derived from basic properties. This language is given a semantics by translating complex classes to SPARQL queries, and its expressiveness is compared to SPARQL in Section 4.

Definition 2 (complex property) A complex property is any of the expressions: p : the property p itself, p of the inverse of the property p, p with the symmetric closure of the property p, trans P the transitive closure of the complex property P ("transitively P "), opt P the reflexive closure of the complex property P ("optionally P ").

OWL allows to declare a name for the inverse of a property, e.g., child is the inverse of parent. In this case, we have that child : and parent of are equivalent. An advantage of our language is that it allows to read all properties in both directions, whether a name for the inverse has been defined or not. Similarly, OWL allows to declare a property as symmetric or transitive, and our language allows to use such closures on-the-fly. For instance, the complex property parent with allows to reach parents and children at the same time, whereas it is unlikely to have a property name defined to this purpose. If a property ancestor is defined, then it is equivalent to trans parent. In the following, we use in as an abbreviation for the complex property opt trans part of. Applying the three closures, opt trans p with, defines an equivalence relation, while opt trans P defines a partial ordering if P is antisymmetric, and a pre-order otherwise.

Definition 3 (complex class) Let V be an infinite set of variables, disjoint with the set of resources R. For every resource r ∈ R, variable v ∈ V , IRI i, complex property P , and complex classes C, C 1 , C 2 , the following expressions are also complex classes: r, ?v, ?, P C, a i, C 1 and C 2 .

Compared to DL languages, the complex class r corresponds to a nominal or enumerated class containing exactly one individual, the anonymous variable ? corresponds to the top concept , the expression P C corresponds to a qualified existential restriction ∃P.C (simply a restriction from now on), the expression a i corresponds to a concept name, and the and corresponds to concept intersection . The addition of variables allows the expression of cyclical graph patterns, like in SPARQL. The notation p : is reminiscent of the notation of valued attributes. For example, in the expression name : "John", name is the attribute, and "John" is the value. The expression can be read "has name John", or "whose name is John". The above query can now be written: a woman and parent : birth : (date : 1642 and place : in VA)

A semantics for our language, and a practical way to compute answers to queries in this language, is obtained by defining a translation to SPARQL.

Definition 4 Let C be a complex class. The SPARQL translation of C is defined by

Γ(C) = SELECT ?x WHERE Γ x (C)
where x ∈ V is a variable not occuring in C, and where Γ x is defined by induction on complex classes: for every complex class C, C 1 , C 2 , and complex property P ,

• Γ x (r) = FILTER { ?x = r }, where r ∈ R is a resource, • Γ x (?v) = FILTER { ?x = ?v }, where v ∈ V is a variable,
• Γ x (?) = {} (the empty graph pattern),

• Γ x (P C) = { { ?x P ?y } Γ y (C) }, where y is a fresh variable,

• Γ x (a i) = { ?x rdf:type i }, where i ∈ I is a class IRI, • Γ x (C 1 and C 2 ) = { Γ x (C 1 ) Γ x (C 2 ) }.
The triples whose predicate is not a basic property can be handled by defining a new property with OWL axioms or deductive rules. It is also possible to rewrite those triples into SPARQL graph patterns, except for transitivity, which requires regular expressions as predicates (nSPARQL [START_REF] Pérez | nSPARQL: A navigational language for RDF[END_REF]):

• ?x p of ?y → ?y p ?x,

• ?x p with ?y → { ?x p ?y } UNION { ?y p ?x },

• ?x opt P ?y → { ?x P ?y } UNION { FILTER { ?x = ?y }.

We can now define the second part of a local view, the extension. It is simply defined as the answers to the SPARQL translation of the query.

Definition 5 (extension) Let C be a complex class. The extension of C, noted ext(C), is the set of resources that are answers to the SPARQL translation of C. Every element of the extension is called an instance of the complex class C.

Given the constraint of a single distinguished variable in SPARQL queries, there may be more efficient ways to compute the extension, compared to generating the SPARQL query and computing its answers. However, the implementation details and optimizations are out of the scope of this paper.

Summarization Index

The third part of the local view is the index which serves as a summary of the extension. Every index term is a descriptor of some or all resources in the extension. Therefore, every index term can be seen as a refinement of the current query. Lemma 7 proves that, in most cases, the extension of the refined query can be reduced to an intersection. Definition 6 (index term) Let q be a complex class representing the query of a local view. A complex class x is an index term of q, which we note x ∈ index (q), if ext(q and x) = ∅.

Lemma 7 Let q, x be complex classes. Unless q and x have variables in common, we have ext(q and x) = ext(q) ∩ ext(x).

This lemma provides a valuable optimization because the query extension ext(q) is already computed in the local view, and the extension of index terms can be cached for the most common of them. The number of index terms can be infinite, but in practice only a limited subset is presented to the user at any given time. Initially, a small index is presented, and then the user can expand it in a controlled way to see more index terms. A number of statistical indicators can be attached to an index term x to qualify its relation to the query q, e.g.:

• count(x, q) = ext(q and x) ,

• precision(x, q) = ext(q and x) ext(q) , Collection des Publications Internes de l'Irisa c IRISA • recall (x, q) = ext(q and x)

ext(x)

.

Instead of presenting the index terms as a flat list, they can be organized into a partial ordering ≤ that reflects subsumption relationships between them. Figure 2 and3 show how this partial ordering can be rendered as trees of complex classes. The number at the left of each index term is its count. Figure 3 gives the number of male Washington's having a given firstname (Figure 3(a)), and being born in a given place (Figure 3(b)). It is not required that this partial ordering be complete w.r.t. subsumption because it does not affect query answering. To one end, we can just rely on the subsumption relationships between class names (rdfs:subClassOf) and property names (rdfs:subPropertyOf) as done in RDFS. On the other end, we can exploit the full reasoning capabilities of OWL-DL to infer subsumption relationships between complex classes and between complex properties. The guiding criteria to design this partial ordering is that it should be intuitive to users (i.e., they can anticipate the infered subsumptions), it should provide enough structure to the index, and it should be of practical complexity.

In the illustrations of this paper, we use only RDFS inference through the properties rdfs:subClassOf and rdfs:subPropertyOf. In the partially ordered index, every class is placed under its superclasses. For instance, a woman ≤ a person ≤ a thing. Every property is placed under its superproperties, and also under its different closures. For instance, father of ≤ parent of ≤ trans parent of. From this ordering of complex properties, restrictions can also be ordered:

P 1 C 1 ≤ P 2 C 2 ⇐⇒ P 1 ≤ P 2 ∧ C 1 ≤ C 2 .
(1)

For instance, father of a man ≤ parent of a person. Every index term is placed under the anonymous variable ?, which then plays the role of the root of the whole index. Similarly, all restrictions in the form P C are grouped under P ?.

We have noted above that a reflexive and transitive complex property, i.e., in the form opt trans P , is a partial ordering. It would be useful that the index reflects this partial ordering through its own partial ordering. This is already the case for the property rdfs:subClassOf (resp. rdfs:subPropertyOf) through the complex classes a i (resp. P C), as explained above. This can be generalized by observing that the following subsumption holds for every complex property P , and every IRIs i 1 , i 2 :

opt trans P i 1 ≤ opt trans P i 2 ⇐⇒ i 1 ∈ ext(opt trans P i 2 ).

(2) This is illustrated in Figure 3(b) with the birth place of male Washington's: e.g., in Westmorland ≤ in VA, because Westmorland ∈ ext(in VA). In fact, the complex class a i is equivalent to type : opt trans rdfs:subClassOf : i, where i is a class IRI. Therefore, the index under this complex class reveals the same class subsumption hierarchy as under a thing. We now list a few other examples in the genealogy ontology:

• place : in ? is the root of a natural hierarchy of locations, from the larger locations to the smaller;

• opt trans parent : is the root of the descendancy chart of the anscestors of the selected people, showing under each individual its children, and this recursively;

• opt trans parent of is the root of the upside-down ancestry chart of the descendants of the selected people, showing under each individual its parents, and this recursively.

Navigation

A local view is determined by its query. The query determines the extension and the index as presented above. By default, the user is initially presented with the local view of the most general query ?, whose extension is the set of all resources defined in the dataset. Alternately, an application can be parameterized by a more specific home query: e.g., the query a person in a genealogical dataset because the focus is then on persons. In their search for information, users need to change the focus, i.e., to change the current query. In retrieval search, users are looking for a particular set of resources, and try and find the query whose extension matches this set of resources. For instance, to answer the question "Which women are married to a Washington?", we can use the query a woman and spouse with lastname : Washington. In exploratory search, users are looking for patterns in data rather than for particular resources. For instance, if the user is interested in the birth place of people having lastname "Washington", she can set the query to lastname : Washington, and then explore the index under the index term birth : place : in ?. She obtains a natural hierarchy of places, where each place is annotated by the proportion of the Washington's that were born in this place. The index also informs about their birth dates, ancestors, descendants, etc. A well informed user can of course directly type in queries. However, as explained in the introduction, this requires not only to have good knowledge of the query language (syntax and semantics), and of the domain-specific vocabulary (e.g., man, place), but also of the contents of the dataset if one wants to avoid empty results. This is paradoxal as the less we know a dataset, the more we need to search it. We propose to define navigation links between local views, so as to guide users. We prove in this section that this guiding is both consistent, i.e., never leads to empty results, and complete, i.e., can lead to arbitrary local views. The index plays a central role in navigation, in addition to summarization. It is really what makes LIS different to other approaches.

There are only three primitive kinds of navigation links: zoom-in, naming, and reversal. The zoom-in applies to an index term, the naming applies to a variable name (generated or user-given), and the reversal applies to a syntactic element of the query. If we see the query in its SPARQL form, the zoom-in extends the graph pattern, while the reversal changes the variable in the SELECT clause, thus changing the point of view. The naming makes a variable of the SPARQL query visible in the LIS query.

Definition 8 (navigation link) A navigation link l is a function that takes a complex class as input (the initial query q), and returns a new complex class as output (the resulting query q ): l(q) = q . For convenience, we note q [l] q , the transition from q to q through the navigation link l. Navigation links can be composed into sequences to form complex navigation links:

q 0 [l 1 ; ...; l n ] q n = q 0 [l 1 ] q 1 ...q n-1 [l n ] q n .
Definition 9 (navigation consistency) A navigation link l is consistent w.r.t. a dataset and an initial query q that has answers, i.e., ext(q) = ∅, if the resulting query l(q) also has answers, i.e., ext(l(q)) = ∅. A set of navigation links is consistent iff every navigation link it contains is consistent.

We now define the three primitive kinds of navigation links and prove under which conditions they are consistent. The zoom-in conjunctively extends the initial query with a complex class.

Definition 10 (zoom-in) Let q be the initial query, and x be a complex class. The zoom-in on x is a navigation link that leads to the query q and x: q [zoom-in x] q and x.

A zoom-in is consistent iff it is applied to an index term, so that every index term represents a consistent navigation link. Every index term leads to its associated refined query (see Definition 6).

Lemma 11 Let q be a query, and index (q) its associated index. For every complex class x, the navigation link

[zoom-in x] is consistent iff x ∈ index (q).
Proof. By definition of index (q) and navigation consistency.

Zoom-in is mostly useful when the extension of the resulting query is strictly smaller. This is obtained when using index terms whose precision is strictly less than 1. This useful distinction can be made visible in the interface by different renderings (e.g., font-color), and annotations (e.g., precision, count).

Naming works similarly to zoom-in, but is expected to apply to a fresh variable, i.e., not occuring in the initial query, while zoom-in is expected to apply to variables already occuring in the initial query.

Collection des Publications Internes de l'Irisa c IRISA Definition 12 (naming) Let q be the initial query, and ?v be a variable. The naming on ?v is a navigation link that leads to the query q and ?v: q [naming ?v] q and ?v.

Lemma 13 Let q be a query. For every variable ?v, the navigation link [naming ?v] is consistent if ?v does not occur in the query q.

Proof. If ?v does not occur in q, then q and ?v is equivalent to q and ?, which is equivalent to q. Therefore, by the hypothesis that ext(q) = ∅, the navigation link [naming ?v] is consistent.

Naming does not change the extension, because it produces a query that is equivalent to the initial query, but it introduces a new variable in the query, and hence in the index. Subsequent zoom-in navigation links on these variables allow to form cycles in the graph pattern of the query.

Like naming, reversal does not change the graph pattern, but it changes the variable in the SELECT clause. Indeed, in a complex class, the focus is only on one variable, and it is useful to change this focus. A difficulty is that not all variables in the SPARQL pattern appear in its corresponding complex class. In a reversal navigation link, the new variable is implicitly designated by a syntactic element of the query, more precisely by a leaf of its syntax tree.

Definition 14 (reversal) Let q be an initial query, and e be a syntactic element of this query. The reversal on e is a navigation link that leads to the query ρ(?, q), where ρ is defined by induction on complex classes (the underlined part indicates in which part of the query the selected element stands): for every complex property P , and complex classes C, C 1 , C 2 ,

• ρ(q , ?) = q ,

• ρ(q , P C) = ρ(P -1 q , C),

• ρ(q , C 1 and C 2 ) = ρ(q and C 2 , C 1 ),

• ρ(q , C 1 and C 2 ) = ρ(q and C 1 , C 2 ),

• ρ(q , C) = q and C, otherwise. This definition needs an inverse operation that is defined by induction on complex properties: (p :) -1 = p of (p with) -1 = p with (opt P ) -1 = opt P -1 (p of) -1 = p :

(trans P ) -1 = trans P -1

We illustrate reversal with two examples, starting with the query already presented earlier: q = a woman and parent : birth : (date : 1642 and place : in VA).

• q [reversal birth] parent of a woman and birth : (date : 1642 and place : in VA) result: "a parent of a woman, born in 1642 in Virginia"

• q [reversal in] place of (birth of parent of a woman and date : 1642) and in VA result: "where in Virginia a parent of a woman was born in 1642"

Lemma 15 A reversal navigation link is necessarily consistent.

Proof. It can be proved that the initial and resulting query of a reversal define the same SPARQL query, up to the renaming of variables, and the possible replacement of the variable in the SELECT clause. If the intial query q has answers, this implies that every variable in the graph pattern has substitution values. Indeed, the graph patterns generated from complex classes contain neither optional patterns, nor union patterns. Therefore, the resulting query q , which has an equivalent graph pattern, also has answers.

We can now define a consistent set of navigation links from a local view.

Definition 16 (local links) Let q be a query defining a local view. The set of local links, noted links(q), is defined as the union of a zoom-in link for each index term x ∈ index (q), a naming link for one fresh variable, and a reversal link for each syntactic element in the query q.

Theorem 17 (navigation consistency) For every query q such that ext(q) = ∅, the set of local links links(q) is consistent.

Collection des Publications Internes de l'Irisa c IRISA Proof. This is a direct consequence of previous definitions and lemmas.

This implies that, given the initial query has answers, a user that only follows local links will never fall in a dead-end, which is a frequent cause of frustration in information systems. An important related issue is completeness, i.e., the ability to reach arbitrary queries by navigation only, rather than with the help of manual query editing.

Definition 18 (navigation completeness) A definition of local links is complete iff for every query q whose extension is not empty, there exists a finite sequence of navigation links q 0 [l 1 ] q 1 ...q n-1 [l n ] q n , where q 0 = ?, q n = q, and for every i ∈ [1, n], the navigation link l i is a local link of its initial query: l i ∈ links(q i-1 ). We call such a sequence, a sequence of local links.

If we have an unlimited index, then navigation is trivially complete. Indeed, if a query q verifies ext(q) = ∅, then it belongs to the index of the query ? because q is equivalent to ? and q. Therefore, q can be reached in one zoom-in link. What is interesting is to prove navigation completeness for a finite index.

Theorem 19 (finite complete index) Let base index (q) be the subset of index (q) restricted to resources (IRIs, literals), variables occuring in q, and the restrictions P ?. The set of local links derived from this base index is finite and complete for navigation.

Proof. The base index is finite because in a given dataset (1) there is a finite number of IRIs, and hence of properties, (2) only literals present in the extension belong to the index, and this extension is always finite, and (3) every query has a finite number of variables.

For completeness, we have to prove that every zoom-in on an index term that is not in the basic index can be decomposed into a sequence of local links that are derived from the base index. This is achieved by an inductive reduction of the excluded index terms (≡ denotes query equivalence):

• q [zoom-in ?v] q and ?v = q [naming ?v] q and ?v, for every variable v / ∈ q

• q [zoom-in ?] q and ? = q [] (q ≡ q and ?) ([] is the empty sequence)

• q [zoom-in P C] q and P C = q [zoom-in P ?] q and P ? [reversal ?] (? and P -1 q ≡ P -1 q) [zoom-in C] P -1 q and C [reversal q] q and P C [zoom-in P ?] is a local link (from the base index) because P ? is more general than P C, which is a local link by hypothesis. [zoom-in C] is also a local link, but not necessarily from the base index (needs to be decomposed further).

• q [zoom-in a i] q and a i = q [zoom-in rdf:type : i] (q and rdf:type : i ≡ q and a i)

• q [zoom-in C 1 and C 2 ] q and (C 1 and C 2 ) = q [zoom-in C 1 ] q and C 1 [zoom-in C 2 ] ((q and C 1 ) and C 2 ≡ q and (C 1 and C 2 )) If q and (C 1 and C 2 ) has answers, then q and C 1 has also answers, because it is more general. Therefore, C 1 ∈ index (q), and C 2 ∈ index (q and C 1 ).

In the base index, the set of resources can be seen as the list of answers to the query, and can be presented page by page, like in web search engines. The set of properties is organised into a subsumption hierarchy that can be expanded on demand by users. Instead of showing up to 12 complex properties for every basic property p, only p : and p of can be displayed. Their various closures are accessible by toggling each closure on/off when applying zoom-in (see check-boxes in Figure 2).

The index computed in our prototype is richer than the base index, in order to provide richer summaries of query results. It contains the hierarchy of classes (a i), and the user can expand restrictions recursively, i.e., each P ? is refined into P C, where C is derived in the same way the main index is derived from ?. Zoom-in is performed by double-clicking an index term, naming is performed by entering a variable name in a text field, and reversal is performed by clicking on a query element. The interface offers three short-hand navigation links on index terms (see buttons in Figure 2):

• home: reset the query to ?,

• pivot C = home; zoom-in C,

• cross P C = zoom-in P C; reversal C.
Collection des Publications Internes de l'Irisa c IRISA Then, the above query a woman and parent : birth : (date : 1642 and place : in VA) is accessible from ? through the following sequence of navigation links: zoom-in a woman; cross parent : ?; cross birth : ?; zoom-in date : 1642; zoom-in place : in VA; reversal a woman. After selecting women, the user moves to their parents, and then to the birth of their parents. By expanding recursively index terms, the user discovers birth dates and places, and select a date (1642), and a place (in VA). Finally, the user comes back to the point of view of women, now restricted to those whose some parent was born in 1642 in Virginia.

Discussion and Conclusion

The contribution of this paper is not about a new query language, but about an interactive navigation process that guides users from query to query, along the LIS principles. The query language proposed here has been driven by LIS constraints (a query denotes a complex class), and the wish to have queries as concise and natural as possible. However, it is interesting to discuss further its expressivity compared to SPARQL [START_REF] Pérez | Semantics and complexity of sparql[END_REF]. The missing graph patterns are the OPTIONAL, UNION, and FILTER patterns. In our case, the OPTIONAL pattern is useless because the SELECT clause has only one variable. Our prototype has already UNION patterns through an or operator but we do not have consistency and completeness results yet about their navigation. It also has negation, and some limited forms of FILTER patterns as predefined classes of literals. For instance, the class match "regexp" denotes the set of all strings that match a regular expression. Similarly, we have classes for intervals and inequalities over numbers and dates. The most important restriction in our queries is the one-variable SELECT clause. However, the index alleviates this restriction to some extent. Suppose the SPARQL query SELECT ?x ?y WHERE { ?x rdf:type gen:man . ?x gen:mother ?y }. By setting the query to a man, and by expanding mother : ?, the index gives for each mother, how many male children she has. A highlighting mechanism allows to select a man in the extension to discover who is his mother; and alternately, to select a mother in the index to discover which are her children. The index is an inverted view over the table of SPARQL results. Each subtree of the index (with count annotation) is a histogram of the values from a column of the table. The highlighting mechanism enables to retrieve the associations between the values of the different columns, i.e., the result tuples.

SPARQL defines updates and rules by using the same graph patterns as in queries. In the same way, we plan to reuse complex classes for specifying updates and rules. Like for queries, we do not expect from users to type updates and rules, and we aim to reuse the local view and navigation links to guide users in the expression of updates and rules.

We have defined local views over RDF(S) datasets that serve both for summarization and navigation. The set of navigation links available in local views is both consistent and complete, thus combining the expressivity of querying languages with the ease-of-use of navigation. Important remaining issues are scalability and ergonomy. Our current prototype is an evolution of an existing LIS (Camelis), and has not yet been optimized w.r.t. these issues. About scalability, everything in our approach can be reduced to answering queries, so that existing results about efficiently answering queries can be reused. If one wants to include more reasoning in the process, it is possible to translate complex classes and properties to OWL query languages (e.g., SPARQL-DL [START_REF] Sirin | SPARQL-DL: SPARQL query for OWL-DL[END_REF], OWL-QL [START_REF] Fikes | OWL-QL -a language for deductive query answering on the semantic web[END_REF]), and reuse existing reasoners. About ergonomy, the index is a new and rich structure that requires and suggests new interfaces. For instance, index terms about dates may be rendered on a calendar, showing graphically the distribution of events over time. The same can be done with places on a map. Like the index, these graphical representations would activable. For instance, the selection of an area on the map would trigger a zoom-in navigation link [START_REF] Bedel | GEOLIS: A logical information system for geographical data[END_REF].

Figure 1 :

 1 Figure 1: A screenshot of the user interface of Camelis, a LIS software.

Figure 2 :

 2 Figure 2: A local view: query (top), extension (right), and index (left).

Figure 3 :

 3 Figure 3: Index subtrees for the query a individual and sex : M and lastname : Washington: (a) under firstname : ?, (b) under birth : place : in ? (@ is used to group resource index terms, and is used to avoid repetition of a same property).

Collection des Publications Internes de l'Irisa c IRISA

see http://www.irisa.fr/LIS/softwares Collection des Publications Internes de l'Irisa c IRISA


Émile Del Éage

WELL-POSEDNESS OF REYNOLDS AVERAGED EQUATIONS FOR COMPRESSIBLE FLUIDS WITH A VANISHING PRESSURE

We show that the Reynolds averaged equations for compressible fluids (neglecting third order correlations) are well-posed in H s when the pressure vanishes in dimensions d = 2 and 3. In order to do this, we show that the system is Friedrichs-symmetrizable. This model belongs to the class of non-conservative hyperbolic systems. Hence the usual symmetrisation method for conservation laws can not be used here.

Introduction and main results

We study the Reynolds averaged equations for compressible fluids, where thirdorder correlations are neglected. This system can be written in Eulerian coordinates as The variables are the averaged density ρ > 0, the averaged velocity v ∈ R d (d = 2 or 3), and P is the Reynolds stress tensor, P ∈ S ++ d (R). The function p is the pressure of the fluid and is a function of the density ρ, through an equation of state p = p(ρ). The map ρ → p(ρ) is supposed to be of class C 1 and nondecreasing. Typical pressure laws are of the form p(ρ) = aρ γ , with a > 0 and γ > 0 two constants.

             ∂ t ρ + div(ρv) = 0, (1.1a)
The tensor P is a classical Reynolds tensor appearing in the Reynolds averaging of turbulent flows for barotropic compressible fluids (see [START_REF] Pope | Turbulent Flows[END_REF], [START_REF] Wilcox | Turbulence Modeling for CFD[END_REF], [START_REF] Mohammadi | Analysis of the k-epsilon turbulence model[END_REF]). It also appears in the description of free surface shear flows, where the averaging operator is the depth averaging (cf. Annexe C, A7 in [START_REF] Richard | Élaboration d'un modèle d'écoulements turbulents en faible profondeur : Application au ressaut hydraulique et aux trains de rouleaux[END_REF] for a derivation of the model). In that latter case, the density ρ must be replaced by the water depth, often denoted h. The pressure is then given by p(h) = gh 2 /2 (cf. [START_REF] Richard | Élaboration d'un modèle d'écoulements turbulents en faible profondeur : Application au ressaut hydraulique et aux trains de rouleaux[END_REF] for instance).

System (1.1) is hyperbolic whenever p ′ (ρ) ≥ 0 and P is definite positive, as it has been proved in [START_REF] Richard | Élaboration d'un modèle d'écoulements turbulents en faible profondeur : Application au ressaut hydraulique et aux trains de rouleaux[END_REF]. Equation (1.1a) shows that the density ρ is conserved. The conservation of momentum ρv also holds: (1.1b) rewrites as

(1.2) ∂ t (ρv) + div(ρv ⊗ v + pI d + ρP ) T = 0.
Date: May 11, 2023.

The author was partially supported by IMPT and INRAE.

1

One can also deduce from (1.1) the conservation of energy:

(1.3) ∂ t e + div(ev + pv + ρP v) = 0, with e := 1 2 ρ|v| 2 + ρE(ρ) + 1 2
Tr(ρP ).

The map ρ → ρE(ρ) is called the volumic internal energy, and is linked to the pressure via the relation p(ρ) = ρ 2 E ′ (ρ). The term ρ|v| 2 /2 is the volumic kinetic energy of the fluid, and the term Tr(ρP )/2 is the energy associated to the tensor P .

In [START_REF] Gavrilyuk | Variational formulation for models of shear shallow water flows and ideal turbulence[END_REF], it was shown that system (1.1) admits a variational formulation, as it is often the case in physics when the energy of a system is conserved. Define the Lagrangian density

(1.4) L(ρ, v, P ) := 1 2 ρ|v| 2 -ρE(ρ) - 1 2 Tr(ρP ),
and the corresponding action

(1.5) A := t1 t0 R d
Ldxdt.

Then one can show that (1.1b) is the Euler-Lagrange equation given by the stationnary action principle applied to the action (1.5), under the two constraints (1.1a) and (1.1c).

The tensor P admits an additional conservation law, sometimes called conservation of enstrophy, that is a consequence of (1.1c) and can be written

(1.6) ∂ t detP ρ 2 + v • ∇ detP ρ 2 = 0.
Note that equation (1.1c) implies that the symmetry of P is conserved by the evolution. Equation (1.6) then implies that, if P (t) ∈ S ++ d (R) for some instant t, then this property is true for all times.

It has been proved in [START_REF] Gavrilyuk | Multi-dimensional shear shallow water flows : problems and solutions[END_REF] that system (1.1) does not admit any further conservation law. Thus, in dimension d = 2 or 3, system (1.1) is not conservative. Hence the usual symmetrisation method of Godunov (cf. [START_REF] Godounov | Classe intéressante de systèmes quasi linéaires[END_REF]) and Lax and Friedrichs (cf. [START_REF] Friedrichs | Systems of Conservation Equations with a Convex Extension[END_REF]) for hyperbolic systems of conservation laws (see for instance [START_REF] Serre | Systems of Conservation Laws 1: Hyperbolicity, Entropies, Shock Waves[END_REF], pages 83-84) can not be used here.

However, one can show that system (1.1) is Friedrichs-symmetrizable when the pressure vanishes. More precisely, we state the following proposition:

Proposition 1. Let d = 2 or 3. Suppose that ρ takes values in R * + and P takes values in S ++ d (R).
Then the two following properties are equivalent:

(1) System (1.1) is Friedrichs-symmetrizable (2)
The pressure p is constant: p ′ (ρ) = 0, or the tensor P is a scalar matrix, i.e. there exists λ = λ(t, x) ∈ R such that P = λI d .

Let us make few comments about this proposition:

• The tensor P = λI d is a solution of system (1.1) only for trivial velocities; hence, for applications of this result, the case p ′ = 0 seems more interesting. • This property holds in the variables (ρ, v, P ). It could be possible that system (1.1), written in different variables, appears to be symmetrizable even when p ′ ̸ = 0.

• When d = 1, system (1.1) is symmetrizable, even when p ′ ̸ = 0. In fact, one can prove that one-dimensional hyperbolic systems are always Friedrichssymmetrizable (cf. [START_REF] Panov | On the problem of symmetrizability for hyperbolic systems of first order[END_REF]). In higher dimension d ≥ 2, this does not hold anymore.

As a consequence of Proposition 1, we have the following result regarding the well-posedness of system (1.1):

Theorem 1. Let d = 2 or 3, s > 1 + d/2 and U := R * + × R d × S ++ d (R). Let Ȳ := (ρ, ū, P ) ∈ U and Y 0 taking values in U such that Y 0 -Ȳ ∈ H s (R d ).
We consider the Cauchy problem associated to (1.1) with initial data Y 0 . There exists T > 0 such that (1.1) with p ′ = 0 has a unique classical solution

Y (t) in C 1 ([0, T ] × R d ) with values in U achieving the initial data Y (0) = Y 0 . Furthermore, Y -Ȳ belongs to C([0, T ], H s (R d )) ∩ C 1 ([0, T ], H s-1 (R d )).
Theorem 1 is a consequence of Proposition 1 and of the theory of well-posedness of Kato for quasilinear evolution equations (cf. [START_REF] Kato | Quasi-linear equations of evolution, with applications to partial differential equations[END_REF]). For a detailed proof of this result, see for instance Sect. 10 in [START_REF] Benzoni-Gavage | Multi-dimensional hyperbolic partial differential equations: First-order systems and applications[END_REF].

System (1.1) has been used over the last years in the modeling of turbulent flows, including for numerical simulations (see [START_REF] Richard | The classical hydraulic jump in a model of shear shallowwater flows[END_REF], [START_REF] Ivanova | Formation and coarsening of roll-waves in shear shallow water flows down an inclined rectangular channel[END_REF], [START_REF] Gavrilyuk | Multi-dimensional shear shallow water flows : problems and solutions[END_REF], [START_REF] Ivanova | Structure of the hydraulic jump in convergent radial flows[END_REF] ). However, the well-posedness of (1.1) in dimension d ≥ 2 is still uncertain today. Theorem 1 states an answer to this question in the case of a vanishing pressure. One could also obtain system (1.1) with p ′ = 0 when modeling a fluid for which the pressure gradient ∇p is negligible compared to the turbulence of the fluid div(ρP ) in (1.1b).

The hypothesis p ′ = 0 can also be found in the litterature, in a model called "pressureless gas dynamics". The pressureless Euler equations are obtained from the Euler equations with a pressure assumed to be 0. The pressureless gas dynamics are used to model astrophysical systems (see [START_REF] Zel | Gravitational instability: An approximate theory for large density perturbations[END_REF] for instance) and is only weakly hyperbolic. As a consequence, phenomena like creation of vacuum or high concentrations (delta shocks) can occur (see for instance [START_REF] Bouchut | On zero pressure gas dynamics[END_REF], [START_REF] Bouchut | Numerical approximations of pressureless and isothermal gas dynamics[END_REF], [START_REF] Berthon | A relaxation scheme for the approximation of the pressureless euler equations[END_REF]). System (1.1) with p ′ = 0 can thus be seen as a hyperbolic version of the pressureless gas model. In this sense, the Reynolds tensor P brings more regularity to the model.

Proof of the proposition

Notations. We denote ∂ i := ∂/∂x i the partial derivative of the variable x i , for

1 ≤ i ≤ d. If f : R d → R is a scalar function, we denote by ∇f ∈ R d the gradient of f , i.e. the vector field of components ∂ i f , 1 ≤ i ≤ d. If Z = (Z 1 , . . . , Z n ) : R d → R d is a vector field, the divergence of Z is the scalar function defined by div(Z) := ∂ 1 Z 1 + • • • + ∂ n Z n .
We also denote by ∂Z/∂x the Jacobian matrix of Z, i.e. the matrix of coefficients (∂Z/∂x) i,j = ∂Z i /∂x j , for 1 ≤ i, j ≤ d.

If Z = (Z i ) 1≤i≤d and Z ′ = (Z ′ i ) 1≤i≤d are two vector fields, we denote Z ⊗ Z ′ the second order tensor defined by Z ⊗ Z ′ := Z(Z ′ ) T , i.e. the matrix of coefficients

(Z ⊗ Z ′ ) i,j = Z i Z ′ j , for 1 ≤ i, j ≤ d. If A : R d → M d (R)
is a second order tensor, we defined the divergence of A as the line vector of R d whose i-th component is given by the divergence of the i-th column of A.

For any positive integer d, we denote I d ∈ M d (R) the identity matrix of size d. We denote S ++ d (R) the set of symmetric definite positive matrices, i.e. the symmetric matrices of size d with a positive spectrum.

We now give the proof of Proposition 1.

Proof. We write system (1.1) in matricial form:

∂ t Y + A(Y, ∇)Y = 0, with Y :=   ρ v P   ∈ R 1+d+d(d+1)/2 and, if ξ = (ξ i ) 1≤i≤d ∈ R d , (2.1) A(Y, ξ) :=   v • ξ ρξ T 0 1 ρ (p ′ (ρ)I d + P )ξ (v • ξ)I d C(ξ) 0 D(ξ) (v • ξ)I d(d+1)/2   .
When d = 2, the symmetric matrix P = (P ij ) 1≤i,j≤2 can be identified as a vector P ∈ R 3 given by P := When d = 3, the symmetric matrix P can be identified as a vector P ∈ R 6 :

P :=         P 11 P 12 P 13 P 22 P 23 P 33         .
The matrices C(ξ) and D(ξ) are then given by

C(ξ) :=   ξ 1 ξ 2 ξ 3 0 0 0 0 ξ 1 0 ξ 2 ξ 3 0 0 0 ξ 1 0 ξ 2 ξ 3   and D(ξ) :=         2(P ξ) 1 0 0 (P ξ) 2 (P ξ) 1 0 (P ξ) 3 0 (P ξ) 1 0 2(P ξ) 2 0 0 (P ξ) 3 (P ξ) 2 0 0 2(P ξ) 3        
, where (P ξ) i denotes the i-th component of the vector P ξ.

We first show the implication (2) ⇒ (1). Namely, if p ′ = 0 or P = λI d , then system (1.1) is Friedrichs-symmetrizable. We thus suppose that p ′ = 0 or P = λI d . Consider S = S(Y ) ∈ S ++ n (R) (with n = (d + 1)(d + 2)/2) defined as a block matrix, compatible with A:

(2.2) S =   1 0 0 0 S 2 0 0 0 S 3   , with S 2 ∈ M d (R) and S 3 ∈ M d(d+1)/2 (R).
Note that S is symmetric definite positive if and only if the matrices S 2 and S 3 are also symmetric definite positive.

We can now compute the product SA by block matrix mutiplication. We obtain that

(2.3) SA =   v • ξ ρξ T 0 1 ρ S 2 (p ′ (ρ)Id + P )ξ (v • ξ)S 2 S 2 C(ξ) 0 S 3 D(ξ) (v • ξ)S 3   Case d = 2. Let us choose S 2 := µP -1 and S 3 := µ   1 2 q 2 11
q 12 q 11 1 2 q 2 12 q 12 q 11 q 11 q 22 + q 2 12 q 12 q 22 1 2 q 2 12

q 12 q 22 1 2 q 2 22   ,
where we denoted (2.4)

P -1 = q 11 q 12 q 12 q 22 ∈ S ++ 2 (R), and (2.5)
µ :=    ρ 2 when p ′ (ρ) = 0, ρ 2 λ p ′ (ρ) + λ when P = λId.
The matrix S 2 is symmetric definite positive. We see that the principal minors of µ -1 S 3 are given by M 1 = 1 2 q 2 11 > 0, M 2 = 1 2 q 2 11 (q 11 q 22 -q 2 12 ) > 0, and M 3 = 1 4 (q 11 q 22 -q 2 12 ) 3 > 0 (recall that P is positive definite). Hence by Sylvester's criterion, S 3 is definite positive, and S, defined by (2.2), is a positive definite matrix.

We compute that

(2.6) 1 ρ S 2 (p ′ (ρ)Id + P ) ξ = ρξ, S 2 C(ξ) = µ q 11 ξ 1 q 11 ξ 2 + q 12 ξ 1 q 12 ξ 2 q 12 ξ 1 q 12 ξ 2 + q 22 ξ 1 q 22 ξ 2 ,
and, since q i1 P 1j + q i2 P 2j = δ ij by (2.4),

S 3 D(ξ) = µ   q 11 ξ 1 q 12 ξ 1 q 12 ξ 1 + q 11 ξ 2 q 22 ξ 1 + q 12 ξ 2 q 12 ξ 2 q 22 ξ 2   = [S 2 C(ξ)] T .
Hence for any Y ∈ U, and for any ξ ∈ R

S 3 := µ         1 2 q 2 11
q 11 q 12 q 11 q 13 1 2 q 2 12 q 12 q 13 1 2 q 2 13 q 11 q 12 q 11 q 22 + q 2 12 q 11 q 23 + q 12 q 13 q 12 q 22 q 12 q 23 + q 22 q 13 q 13 q 23 q 11 q 13 q 11 q 23 + q 13 q 12 q 11 q 33 + q 2 13 q 12 q 23 q 12 q 33 + q 23 q 13 q 13 q 33 1 2 q 2 12 q 12 q 22 q 12 q 23 1 2 q 2 22 q 22 q 23 1 2 q 2 23 q 12 q 13 q 12 q 23 + q 13 q 22 q 12 q 33 + q 13 q 23 q 22 q 23 q 22 q 33 + q 2 23 q 23 q 33 1 2 q 2 13 q 13 q 23 q 13 q 33 1 2 q 2 23 q 23 q 33

1 2 q 2 33        
, where we denoted again

P -1 :=  
q 11 q 12 q 13 q 12 q 22 q 23 q 13 q 23 q 33   .

We see that S 3 is symmetric. Furthermore, the principal minors of µ -1 S 3 are given by M 1 = q 2 11 /2 > 0, M 2 = q 2 11 (q 11 q 22 -q 2 12 )/2 > 0, M 3 = q 3 11 det(P -1 )/2 > 0, M 4 = q 11 (q 11 q 22 -q 2 12 ) 2 det(P -1 )/4 > 0, M 5 = (q 11 q 22 -q 2 12 ) 2 det(P -1 ) 2 /4 > 0 and M 6 = det(P -1 ) 4 /8 > 0. Hence, by Sylvester's criterion, S 3 is definite positive and S is symmetric definite positive.

We also check that

S 3 D(ξ) = [S 2 C(ξ)] T .
Hence equation (2.3) shows that SA is symmetric, and, consequently, (1.1) is Friedrichs-symmetrizable when d = 3.

We now show that (1) ⇒ (2). Suppose that system (1.1) is Friedrichs-symmetrizable, i.e. there is a matrix S such that the product SA is symmetric.

We write S as a block matrix, compatible with A:

S :=   S 1 α β α T S 2 γ β T γ T S 3   .
We compute the product SA by block multiplication. Since SA is symmetric, for any block of SA, denoted (SA) i,j (1 ≤ i, j ≤ 3), we must have (SA) i,j = (SA) T j,i . For i = j = 3, we obtain the constraint

γ T C(ξ) + (v • ξ)S 3 = γ T C(ξ) + (v • ξ)S 3 T .
Since S 3 is symmetric, we deduce that the product γ T C(ξ) is symmetric, for any ξ ∈ R d . By computing explicitely the product, we obtain that the only possibility is that γ = 0. For i = 1 and j = 3, we obtain the constraint T Solving the linear system (2.7) for S 2 , S 3 and β gives after some computations that there exists two constants λ 1 , λ 2 such that (2.8) S 2 = λ 1 P -1 and β = λ 2 (q 11 , 2q 12 , q 22 ) when d = 2, λ 2 (q 11 , 2q 12 , 2q 13 , q 22 , 2q 23 , q 33 ) when d = 3.

Note that it follows from these computations that βD(ξ) = 2λ 2 ξ T . For i = 1 and j = 2 we obtain the constraint (2.9) 1 ρ S 2 (p ′ (ρ)Id + P )ξ = S 1 ρξ T + βD(ξ) T = (S 1 ρ + 2λ 2 )ξ.

Equation (2.9) implies that S 2 is proportional to (p ′ (ρ)Id + P ) -1 . Since S 2 is also proportional to P -1 by (2.8), we obtain that the two matrices P and P + p ′ (ρ)Id are proportional (recall that S 2 is invertible). Hence p ′ = 0 or P = λId. □

∂

  t v + (v • ∇v) + 1 ρ∇p + div(ρP ) T = 0, (1.1b)∂ t P + (v • ∇)P +

2P 11 ξ 1 + 2P 12 ξ 2 0 P 21 ξ 1 + P 22 ξ 2 P 11 ξ 1 + P 12 ξ 2 0 2P 12 ξ 1 + 2P 22 ξ 2

 1121212 The matrices C(ξ) and D(ξ) are then given byC(ξ) := ξ 1 ξ 2 0 0 ξ 1 ξ 2 and D(ξ) :=  

[

  αC(ξ) + (v • ξ)β] T = (v • ξ)β T + 1 ρ γ T (p ′ (ρ)Id + P )ξ.Since γ = 0, we obtain that αC(ξ) = 0, for any ξ ∈ R d . By computing explicitely the product, we also obtain that α = 0. Hence S has to be of the formS =   S 1 0 β 0 S 2 0 β T 0 S 3   .

For i = 2

 2 and j = 3, we obtain the constraint (2.7)ρβ T ξ T + S 3 D(ξ) = [S 2 C(ξ)]

  2 , the matrix S(Y ) is symmetric definite positive and (2.3) shows that the matrix S(Y )A(Y, ξ) is symmetric. As a consequence, (1.1) is Friedrichs-symmetrizable when d = 2.Case d = 3. Define again S by equation (2.2). Choose S 2 = µP -1 with µ as in (2.5), such that S 2 is symmetric definite positive and (2.6) holds again. Define S 3 by

Aix Marseille Univ., CNRS, Centrale Marseille, I2M UMR CNRS 7373, 13000 Marseille, France

Univ. Grenoble Alpes, CNRS, INRAE, IRD, Grenoble INP, IGE,

Grenoble,FranceEmail address: emile.deleage@univ-amu.fr