11th International Workshop on Uncertainty Reasoning for the Semantic Web (URSW 2015)

Keywords

• Proceedings

-

collocated with the 14th International Semantic Web Conference (ISWC 2015)

Foreword

This volume contains the papers presented at the 11th International Workshop on Uncertainty Reasoning for the Semantic Web (URSW 2015), held as a part of the 14th International Semantic Web Conference (ISWC 2015) at Bethlehem, USA, October 12, 2015. 4 technical papers and 2 short papers were accepted at URSW 2015. All the papers were selected in a rigorous reviewing process, where each paper was reviewed by three program committee members.

The International Semantic Web Conference is a major international forum for presenting visionary research on all aspects of the Semantic Web. The International Workshop on Uncertainty Reasoning for the Semantic Web provides an opportunity for collaboration and cross-fertilization between the uncertainty reasoning community and the Semantic Web community.

We wish to thank all authors who submitted papers and all workshops participants for fruitful discussions. We would like to thank the program committee members for their timely expertise in carefully reviewing the submissions.

October 2015 III

Fernando Bobillo

Rommel N. Carvalho

Davide Ceolin Paulo C. G. da Costa Claudia d'Amato

Nicola Fanizzi Kathryn B. Laskey

Kenneth J. Laskey Thomas Lukasiewicz

Trevor Martin Matthias Nickles

Michael Pool

URSW 2015

Workshop Organization

Organizing Committee

Fernando Bobillo (University of Zaragoza, Spain)

Rommel N. Carvalho (Universidade de Bras lia, Brazil) Paulo C. G. da Costa (George Mason University, USA) Davide Ceolin (VU University Amsterdam, The Netherlands) Claudia d'Amato (University of Bari, Italy) Nicola Fanizzi (University of Bari, Italy) Kathryn B. Laskey (George Mason University, USA) Kenneth J. Laskey (MITRE Corporation, USA) Thomas Lukasiewicz (University of Oxford, UK) Trevor Martin (University of Bristol, UK) Matthias Nickles (National University of Ireland, Ireland) Michael Pool (Goldman Sachs, USA)

Program Committee

Fernando Bobillo (University of Zaragoza, Spain)

Rommel N. Carvalho (Universidade de Bras lia, Brazil) Davide Ceolin (VU University Amsterdam, The Netherlands) Paulo C. G. da Costa (George Mason University, USA) Fabio Gagliardi Cozman (Universidade de Sa~o Paulo, Brazil) Claudia d'Amato (University of Bari, Italy) Nicola Fanizzi (University of Bari, Italy) Marcelo Ladeira (Universidade de Bras lia, Brazil) Kathryn B. Laskey (George Mason University, USA) Kenneth J. Laskey (MITRE Corporation, USA) Thomas Lukasiewicz (University of Oxford, UK) Trevor Martin (University of Bristol, UK) Alessandra Mileo (DERI Galway, Ireland) Matthias Nickles (National University of Ireland, Ireland) Je Z. Pan (University of Aberdeen, UK) Rafael Pen~aloza (TU Dresden, Germany) Michael Pool (Goldman Sachs, USA) Livia Predoiu (University of Mannheim, Germany) Guilin Qi (Southeast University, China) David Robertson (University of Edinburgh, UK) Daniel Sanchez (University of Granada, Spain) V Giorgos Stoilos (National Technical University of Athens, Greece) Umberto Straccia (ISTI-CNR, Italy) Matthias Thimm (Universitat Koblenz-Landau, Germany) Peter Vojtas (Charles University Prague, Czech Republic)

Table of Contents

URSW 2015 Technical Papers { Evaluating Uncertainty in Textual Document

Fadhela Kerdjoudj and Olivier Cure { PR-OWL 2 RL - A Language for Scalable Uncertainty Reasoning on the Semantic Web Laecio L. dos Santos, Rommel N. Carvalho, Marcelo Ladeira, Li Weigang and Gilson L. Mendes { E cient Learning of Entity and Predicate Embeddings for Link Prediction in Knowledge Graphs Pasquale Minervini, Claudia d'Amato, Nicola Fanizzi and Floriana Esposito { Probabilistic Ontological Data Exchange with Bayesian Networks Thomas Lukasiewicz, Maria Vanina Martinez, Livia Predoiu and Gerardo I. Simari

URSW 2015 Short Papers { Re ning Software Quality Prediction with LOD

Davide Ceolin, Till Dohmen and Joost Visser { Reducing the Size of the Optimization Problems in Fuzzy Ontology Reasoning Fernando Bobillo and Umberto Straccia 1-13 14-25 26-37 38-49 50-53 54-59 VII

Evaluating Uncertainty in Textual Document

Fadhela Kerdjoudj1,2 and Olivier Cur´e1,3

Abstract. In this work, we consider that a close collaboration between the research fields of Natural Language Processing and Knowledge Representation becomes essential to fulfill the vision of the Semantic Web. This will permit to retrieve information from vast amount of textual documents present on the Web and to represent these extractions in an amenable manner for querying and reasoning purposes. In such a context, uncertain, incomplete and ambiguous information must be handled properly. In the following, we present a solution that enables to qualify and quantify the uncertainty of extracted information from linguistic treatment. 1

Introduction Textual documents abound on the World Wide Web but efficiently retrieving information from them is hard due to their natural language expression and unstructured characteristics. Indeed, the ability to represent, characterize and manage uncertainty is considered as a key factor for the success of the Semantic Web [ 12 ]. The accurate and exhaustive extraction of information and knowledge is nevertheless needed in many application domains, e.g., in medicine to comprehend the meaning of clinical reports or in finance to analyze the trends of markets. We consider that together with techniques from Natural Language Processing (NLP), best practices encountered in the Semantic Web have the potential to provide a solution to this problem. For instance, NLP can support the extraction of named entities as well as temporal and spatial aspects, while the Semantic Web is able to provide an agreed upon representation as well as some querying and reasoning facilities. Moreover, by consulting datasets form Linked Open Data (LOD), e.g., DBpedia, Geonames, we can enrich the extracted knowledge and integrate it to the rest of the LOD.

The information contained in Web documents can present some imperfection, it can be incomplete, uncertain and ambiguous. Therefore, the texts content can be called into question, it becomes necessary to qualify and possibly quantify these imperfections to present to the end user a trusted extraction. However, qualification or quantification is a difficult task for any software application. In this paper, we focus on the uncertainty aspect and trustworthiness of the provided information in the text. A special attention of our work has been devoted to representing such information within the Resource Description Framework (RDF) graph model. The main motivation being to benefit from querying facilities, i.e., using SPARQL.

Usually, uncertainty is represented using reification, but this representation failed in representing uncertainty on triple property. Indeed, the reification does not identify which part of the triple (subject, predicate or the object) is uncertain. Here, we intend to manage these cases of uncertainties, as expressed in Example 1, while in the first sentence, the uncertainty concerns all the moving action (including, the agent, the destination and the date), in the second, the author expressed an uncertainty only on the date of the moving.

Example 1. 1. The US president probably visited Cuba this year. 2. The US president visited Cuba, probably this year.

We based our approach on an existing system developed at GEOLSemantics4, a french startup with expertise in NLP. This framework mainly consists of a deep morphosyntactic analysis and an RDF triple creation using trigger’s detection. Triggers are composed of one or several words (nouns, verbs, etc.) that represent a semantic unit denoting an entity to extract. For instance, the verb ”go” denotes a Displacement. The RDF graph obtained complies with an ontology built manually to support different domains such as Security and Economics. Actually, our framework consists of a set of existing vocabularies (such as Schema.org5, FOAF6, Prov7) to enrich our own main ontology, denoted geol. This ontology contains the general classes which are common to many domains: – Document : Text, Sentence, Source, DateIssue, PlaceIssue, etc. – Named entities : Person, Organization, Location, etc. – Actions : LegalProceeding, Displacing, etc. – Events : SocialEvent, SportEvent, FamilialEvent, etc.

The contributions of this paper are two-fold: (1) We present a fine-grained approach to quantify and qualify the uncertainty in the text based on uncertainty markers; (2) We present an ontology which handles this uncertainty both at the resource and property level. This representation of uncertainty can be interrogated with a rewriting of SPARQL query.

The paper is organized as follows. Section 2 describes related work to uncertainty handling in Semantic Web. In Section 3, we present how to spot uncertain information in the text using specific markers. In Section 4, we propose an RDFbased representation of uncertainty in knowledge extraction. In Section 5, a use case is depicted with some SPARQL queries. Finally, we conclude in Section 6. 4 http://www.geolsemantics.com/ 5 http://schema.org/docs/schemaorg.owl 6 http://xmlns.com/foaf/spec/ 7 http://www.w3.org/TR/prov-o/

Related work Integration of imprecise and uncertain concepts to ontologies has been studied for a long time by the Semantic Web community [ 13 ]. To tackle this problem, different frameworks have been introduced: Text2Onto [ 4 ] for learning ontologies and handling imprecise and uncertain data, BayesOWL [ 7 ] based on Bayesian Networks for ontologies mapping. In [ 6 ], the authors propose a probabilistic extension for OWL with a Bayesian Network layer for reasoning. Actually, fuzzy OWL [ 2, 20 ] was proposed to manage, in addition to uncertainty, some other text imperfection (such as imprecision and vagueness) with the help of fuzzy logics. Moreover, W3C Uncertainty Reasoning for the World Wide Web Incubator Group (URW3-XG) [ 12 ] describes an ontology to annotate uncertain and imprecise data. This ontology focuses on the representation of the nature, the model, the type and the derivation of uncertainty. This representation is really interesting but unfortunately does not show how to link the uncertainty to the concerned knowledge described in the text.

However, in all these works, the uncertainty was considered as a metadata. The ontologies which handle uncertainty are proposed to either create a fuzzy knowledge base (fuzzy ABox, fuzzy TBox, fuzzy Rbox) or to associate each class of the ontology to a super class which denotes the uncertain or fuzzy concept. To each axiom is associated a truth degree in [ 0,1 ]. Therefore, the user is required to handle two knowledge bases in parallel. The first one is dedicated to certain knowledge whereas the second is dedicated to uncertain knowledge. This representation could induce some inconsistencies between the knowledge bases. From a querying perspective this representation is also not appealing since it forces the user to query both bases and then combine the results. In order to avoid these drawbacks, we propose in this paper, a solution to integrate uncertain knowledge to the rest of the extraction. The idea is to ensure that all extracted knowledge, either be it certain or uncertain, is managed within the same knowledge base. This approach aims at ensuring the consistency of the extracted knowledge and eases its querying.

Moreover, it is worth noting that linguistic processing carried out on uncertainty management notably, Saur`ı[ 19 ] and Rubin [ 17 ][ 18 ] works, they payed attention to different modalities and polarity to characterize uncertainty/certainty. The first one [ 19 ], considers two dimensions. Each event is associated to a factual value represented as a tuple < mod, pol > where mod denotes modality and distinguishes among: certain, probable, possible and unknown, pol denotes polarity values which are positive, negative and unknown.

In [ 17 ][ 18 ] four dimensions have been considered: – certainty level: absolute, high, moderate or low. – author perspective: if it is his/her point of view or a reported speech. – focus: if it is an abstract information (opinion, belief, judgment...) or a factual one (event, state, fact...). – time: past, present, future. This model is more complete even if it does not handle negation. However, the authors do not explain how to combine all these dimensions to get a final interpretation to a given uncertainty. In this paper, we explain how to detect uncertainty in textual document and how to quantify it to get a global interpretation. 3

Uncertainty detection in the text The Web contains a huge number of documents from heterogeneous sources like forums, blogs, tweets, newspaper or Wikipedia articles. However, these documents cannot be exploited directly by programs because they are mainly intended for humans. Before the emergence of the Semantic Web, only human beings could access the necessary background knowledge to interpret these documents. In order to get a full interpretation of the text content, it is necessary to consider the different aspects of the given information. Some piece of information can be considered as “perfect” only if it contains precise and certain data. This is rarely the case even for a human reader with some context knowledge. Indeed, the reliability of the data available on the Web often needs to be reconsidered, uncertainty, inconsistency, vagueness, ambiguity, imprecision, incompleteness and others are recurrent problems encountered in data mining. According to [ 9 ] the information can be classified into two categories : subjective and objective. An information is objective or quantitative if it indicates an observable, i.e., something which is able to be counted for example. The other category is the subjective (qualitative) information. It can describe the opinion of the author, he may express his own belief, judgment, assumption, etc. Therefore, the second one is subject to contain imperfect data. Then, it becomes necessary to incorporate these imperfections within the representation of the extracted information.

In this paper, we are interested in the uncertainty aspect. In domains such as information theory, knowledge extraction and information retrieval, the term uncertainty refers to the concept of being unsure about something or someone. It denotes a lack of conviction. Uncertainty is a well studied form of data imperfection, but it is rarely considered at the knowledge level during extraction processing. Our approach consists in considering the life cycle of the knowledge from the data acquisition to the final RDF representation steps, i.e., generating and persisting the knowledge as triples.

Evaluating uncertainties in text As previously explained, the text may contain several imperfections which can affect the trustworthiness of an extracted action or event. So, during the linguistic processing, we need to pay attention to the modalities of the verb which indicate how the action or the event had happened, or how it will. Actually, the text provides information about the epistemic stance of the author, that he often commits according to his knowledge, singular observation or beliefs [ 16 ]. Moreover, natural languages offer several ways to express uncertainty, usually expressed using linguistic qualifiers. According to [ 14, 8, 1 ] uncertainty qualifiers can be classified as follows: – verbal phrases e.g., as likely as, chances are, close to certain, likely, few, high probability, it could be, it seems, quite possible. – expression of uncertainty with quantification all, most, many, some, etc., – modal verbs e.g., can, may, should. – adverbs, e.g., roughly, somewhat, mostly, essentially, especially, exceptionally, often, almost, practically, actually, really. – speculation verbs e.g., suggest, suppose, suspect, presume. – nouns e.g., speculation, doubt, proposals. – expressions e.g., raise the question of, to the best of our knowledge, as far as

I know.

All these markers help to detect and identify the uncertainty with different intensities. This helps in evaluating the confidence degree associated to the given information. For example : it may happen is less certain that it will probably happen. It is also necessary to consider modifiers such as less, more, very. Depending on the polarity of each modifier we add or subtract a predefined real number α, set to 0.15 in our experiment, to the given marker’s degree. We base our approach on a natural language processing. This processing indicates syntactic and semantic dependencies between words. From these dependencies we can identify the scope of each identifier in the text. Once these qualifiers are identified, the uncertainty of the knowledge can be specified and then quantified. By quantifying, we mean attributing a confidence degree which indicates how much we can trust the described entity. To this end, we associate to each marker a probabilistic degree. We defined three levels of certainty: (i) high=0.75, (ii) moderate=0.50, (iii) low=0.25. Moreover, we also base this uncertainty quantification on previous works in this field such as [ 3, 11 ] which define a mapping between the confidence degree and each uncertainty marker. This mapping is called Kent’s Chart and Table 1 provides an extract of it. certain 100 almost certain, believe, evident, little doubt 85-99 fairly certain, likely, should be, appear to be 60-84 have chances 40-59 probably not, fairly uncertain, is not expected 15-39 not believe, doubtful, not evident 1-14

However, uncertainty markers are not the only way to generate uncertainty. Reported speech and future timeline are also considered as uncertainty sources. These will be taken into account when the final uncertainty weight will be calculated. We notice that the trust of the reported speech depends of different parameters which affect the trust granted to its content: – the author of the declaration: if the author name is cited, if the author has an official role (prosecutor, president...). – the nature of the declaration: if it is an official declaration, a personal opinion, a rumor...

Example 2. A crook who burglarized homes and crashed a stolen car remains on the loose, but he probably left Old Saybrook by now, police said Thursday. In Example 2, we can identify two forms of uncertainty. First, the author explicitly expresses, using the term (probably), an uncertainty about the fact that the crook left the city. The second one is related to the reported speech which comes from the police and is not assumed to be a known fact.

Therefore, for a given information described in the text, many sources of uncertainty can occur, then, it is necessary to combine all these uncertainties in order to get a final confidence degree to be attributed to the extracted information. With regard to this issue, we chose a Bayesian approach to combine all uncertainties to the concerned information. Indeed Bayesian network are well suited to our knowledge graph which is a directed acyclic graph. This choice is also motivated by the dependency that exists between children of uncertainty nodes. Indeed, to calculate the final degree of uncertain information, we need to consider its parents, if they contain uncertainty, then the conditional probabitlity related to this parent is reverberated on the child. 4

RDF representation of uncertainty In order to extract complete and relevant knowledge, we consider the uncertainty as an integral part of the knowledge instead of integrating it as an annotation. Usually, uncertainty is added as assertions to triples (the uncertainty assigned to each extracted knowledge). So, we represent it with some reification as recommended by [ 5 ]. Nevertheless, we encountered some difficulties to represent uncertainty on triples’ predicates, as opposed to the whole triple. In the second sentence of Example 1, the uncertainty does not concern the whole moving but only its date. Only one part of the event is uncertain and the RDF representation has to take this into account. In fact, we cannot indicate using reification which part of the triple is uncertain, as shown in Figure 1, with reification, we give the same representation to both sentences in Example 1 even if they express different information. Indeed, reified statements cannot be used in semantic inferences, and are not asserted as part of the underlying knowledge base [ 21 ]. The reified statement and the triple itself are considered as different statements. So, due to its particular syntax (rdf:Statement) the reified triple can hardly be related to other triples in the knowledge base [ 15 ]. Moreover, using blank node to identify the uncertain statement prevents from obtaining good performance [ 10 ]. Indeed, writing queries over RDF data sets involving reification becomes inconvenient. Especially, for one to refer to a reified triple, we need to use four additional triples linked by a blank node.

To deal with previous issues, we propose the UncertaintyOntology ontology which contains a concept (Uncertainty), a datatype property (weight which have Uncertainty as its domain and real values as range) and object properties (isUncertain and hasUncertainProp which respectively denote an uncertain individual (Uncertainty as domain and owl:Thing as range) and an uncertain property of a given individual (Uncertainty as Domain and owl:Thing as Range). This ontology can easily be integrated with our geol ontology or with any other ontology requiring some support for uncertainty.

This ontology (UncertaintyOntology ) handles uncertainty occurring on each level of the triple. If the uncertainty concerns the resource, which denotes a subject or an object triple, so the property isUncertain is employed. If the triple’s predicate is uncertain then we use hasUncertainProp to indicate the uncertainty. UncertainOntology is domain independent, it can be added to any other ontology since we assume that uncertainty occurs on each part of the sentence in a text.

To illustrate this representation, we provide in Figure 2, the RDF representation of Example 1’s sentences. In the first sentence (on the left side), the uncertainty concerns the following triples : :id1Transfer, displaced, :id1USPresident. :id1Transfer, locEnd, :id1Cuba. :id1Transfer, onDate, :id1ThisYear. As we based on Bayesian approach, all these triples have an uncertainty of 0.7, expressed using the uncertainty marker probably.

Whereas, in the second sentence, the uncertainty concerns only the property onDate, so, the triple :id1Transfer, onDate, :id1ThisYear. is uncertain.

Finally, we conclude that using this RDF representation, we identify three different cases of triple uncertainty. Figure 4 shows the representation of different patterns of uncertainty in RDF triples. Pattern 1 describes uncertainty on the object of the triple. Pattern 2 describes uncertainty on the subject and finally, pattern 3, uncertainty on the property.

This representation of uncertainty is more compact than reification and improves user understanding regarding the RDF graph.

SPARQL Querying with uncertainty The goal of our system is to enable end-users to query the extracted information. These queries take into account the presence of uncertainties by going through a rewriting. Our system discovers if such a rewriting is necessary by executing the following queries. First, we list all uncertain properties, using the query in Listing 1.1. The result is a set of triples (s,p,o) where p is an uncertain property. PREFIX gs :< http :// www . geolsemantics . com / onto #> Select ?s ? prop ?o Where { ?s gs : hasUncertainProp ?u. ?u gs : weight ? weight .

?u ? prop ?o. }

Listing 1.1. SPARQL query Select uncertain properties Then, we check if the predicates of each triple in the entry query appear in the result set. If so, we rewrite the query by adding the uncertainty on the given predicate using the pattern query in Listing1.2. Finally, we inspect the query PREFIX gs :< http :// www . geolsemantics . com / onto #> Select ?p ? weight Where {...

?u gs : isUncertain ?p.

?u gs : weight ? weight . ...}

Listing 1.2. SPARQL query Select uncertain resources result set of the rewritten query, in order to check if an uncertainty occurs on each resource (subject and/or object) extracted.

Furthermore, if a user wants to know the list of uncertainties in a given text, the query in Listing 1.3 is used to extract all uncertain data explicitly expressed. We consider that each linguistic extraction is represented according to the schema presented in Section 4. Our goal is now to provide a query interface to the end-user and to qualify the uncertainty associated to each query answer. Of course, the uncertain values that we are associating with the different distinguished variables of a query are directly emerging from the ones we are representing in our graph and which has been described in Section 4. Our system accepts any SPARQL 1.0 queries from the end-user. For testing reasons, we also have defined a set of relevant predefined queries, e.g., the query in Example 3. PREFIX gs :< http :// www . geolsemantics . com / onto #> PREFIX rdf :< http :// www . w3 . org /1999/02/22 - rdf - syntax - ns #> PREFIX v:< http :// www . w3 . org /2006/ vcard / ns #> SELECT distinct ? concept_uncertain ? obj ? weight WHERE { { ?u a gs : Uncertainty . ?u gs : isUncertain ? concept_uncertain . ?u gs : weight ? weight ? u2 a gs : Uncertainty . ? u2 gs : weight ? weight . ?s ? hasUncertainProp ? u2 . ? u2 ? prop ? obj .}

Listing 1.3. SPARQL query : Select all uncertainties in the text Example 3. Let us consider the query in Listing 1.4.

PREFIX gs :< http :// www . geolsemantics . com / onto #> PREFIX rdf :< http :// www . w3 . org /1999/02/22 - rdf - syntax - ns #> PREFIX v:< http :// www . w3 . org /2006/ vcard / ns #> Select ? date Where { ?t gs : displaced ?p. ?p gs : role " president ". ?t gs : locEnd ?l. ?l v: location - name " Cuba ".

?t gs : onDate ? date .

Listing 1.4. SPARQL query : When did the president go to Cuba?

In order to make query submission easier for the end-user, we do not impose the definition of the triple patterns associated to uncertainty handling. Hence, the end-user just submits a SPARQL query without caring where the uncertainties are. Considering query processing, this implies to reformulate the query before its execution, i.e., to complete the query such that its basic graph pattern is satisfiable in the face of triples using elements of our uncertain ontology.

We can easily understand that a naive reformulation implies a combinatorial explosion. This has direct impact on the efficiency of the query result set computation. This can be prevented by rapidly identifying the triple patterns of a query that are subject to some uncertainty. In fact, since our graphs can only represent uncertainty using one of the three patterns presented in Figure 4, we PREFIX gs :< http :// www . geolsemantics . com / onto #> PREFIX rdf :< http :// www . w3 . org /1999/02/22 - rdf - syntax - ns #> PREFIX v:< http :// www . w3 . org /2006/ vcard / ns #> Select ? date ?w Where {{ ?t gs : displaced ?p. ?p gs : role " president ". ?t gs : locEnd ?l. ?l v: location - name " Cuba ". ?t gs : onDate ? date . ?t gs : displaced ?p. ?p gs : role " president ". ?t gs : locEnd ?l. ?l v: location - name " Cuba ". ?t gs ; hasUncertainProp ?u. ?u gs : onDate ? date .

?u gs : weight ?w.

Listing 1.5. Uncertainty query : When did the president go to Cuba? can go through a pre-processing step that indexes these triples. To do so, we use a set of SPARQL queries (see Listing 1.1 and 1.2 which respectively retrieve the properties and subject with their weights). These values are stored in hash tables for fast access.

Therefore, Listing 1.5 corresponds to the rewriting of Listing 1.4. We introduced the uncertainty option and obtained the following results : Sentence Result Uncertainty Uncertainty Detail (1) ?date = “20150101-20151231” 0.7 On the subject (2) ?date = “20150101-20151231” 0.7 On the predicate 6

Conclusion and Perspectives In this article, we addressed the quantification and qualification of uncertain and ambiguous information extracted from textual documents. Our approach is based on a collaboration between Natural Language Processing and Semantic Web technologies. The output of our different processing units takes the form of a compact RDF graph which can be queried with SPARQL queries and reasoned over using ontology based inferences. However, some issues are still unresolved, even for the linguistic community, such as: distinguish between deontic and epistemic meaning. Example: “He can practice sport.” One can interpret this information as a permission and an other as an ability or a certainty. This work mainly concerns the uncertainty expressed in the text, for future work we intend to consider the trust guaranteed to the source of the text. Indeed, the source can influence the trustworthiness and the reliability of the declared information. Moreover, we plan to consider additional aspects of the information, such as polarity. Probabilistic Ontological Data Exchange

with Bayesian Networks Thomas Lukasiewicz1, Maria Vanina Martinez3,

Livia Predoiu12, and Gerardo I. Simari3 Abstract. We study the problem of exchanging probabilistic data between ontology-based probabilistic databases. The probabilities of the probabilistic source databases are compactly encoded via Boolean formulas with the variables adhering to the dependencies imposed by a Bayesian network, which are closely related to the management of provenance. For the ontologies and the ontology mappings, we consider different kinds of existential rules from the Datalog+/– family. We provide a complete picture of the computational complexity of the problem of deciding whether there exists a probabilistic (universal) solution for a given probabilistic source database relative to a (probabilistic) ontological data exchange problem. We also analyze the complexity of answering UCQs (unions of conjunctive queries) in this framework. 1 Large volumes of uncertain data are best modeled, stored, and processed in probabilistic databases [ 22 ]. Enriching databases with terminological knowledge encoded in ontologies has recently gained increasing importance in the form of ontology-based data access (OBDA) [ 21 ]. A crucial problem in OBDA is to integrate and exchange knowledge. Not only in the context of OBDA, but also in the area of the Semantic Web, there are distributed ontologies that we may have to map and integrate to enable query answering over them. Here, apart from the uncertainty attached to source databases, there may also be uncertainty regarding the ontology mappings establishing the proper correspondence between items in the source ontology and items in the target ontology. This especially happens when the mappings are created automatically.

Data exchange [ 11 ] is an important theoretical framework used for studying datainteroperability tasks that require data to be transferred from existing databases to a target database that comes with its own (independently created) schema and schema constraints. The expressivity of the data exchange framework goes beyond the classical data integration framework [ 17 ]. For the translation, schema mappings are used, which are declarative specifications that describe the relationship between two database schemas. In classical data exchange, we have a source database, a target database, a deterministic mapping, and deterministic target dependencies. Recently, a framework for probabilistic data exchange [ 10 ] has been proposed where the classical data exchange framework based on weakly acyclic existential rules has been extended to consider a probabilistic source database and a probabilistic source-to-target mapping.

In this paper, we study an expressive extension of the probabilistic data exchange framework in [ 10 ], where the source and the target are ontological knowledge bases, each consisting of a probabilistic database and a deterministic ontology describing terminological knowledge about the data stored in the database. The two ontologies and the mapping between them are expressed via existential rules. Our extension of the data exchange framework is strongly related to exchanging data between incomplete databases, as proposed in [ 3 ], which considers an incomplete deterministic source database in the data exchange problem. However, in that work, the databases are deterministic, and the mappings and the target database constraints are full existential rules only. In our complexity analysis in this paper, we consider a host of different classes of existential rules, including some subclasses of full existential rules. In addition, our source is a probabilistic database relative to an underlying ontology.

Our work in this paper is also related to the recently proposed knowledge base exchange framework [ 2, 1 ], which allows knowledge to be exchanged between deterministic DL-LiteRDF S and DL-LiteR ontologies. In this paper, besides considering probabilistic source databases, we are also using more expressive ontology languages, since already linear existential rules from the Datalog+/– family are strictly more expressive than the description logics (DLs) DL-LiteX of the DL-Lite family [ 9 ] as well as their extensions with n-ary relations DLR-LiteX . Guarded existential rules are sufficiently expressive to model the tractable DL E L [ 4, 5 ] (and E LIf [ 16 ]). Note that existential rules are also known as tuple-generating dependencies (TGDs) and Datalog+/– rules [ 7 ]. The main contributions of this paper are summarized as follows. − We introduce deterministic and probabilistic ontological data exchange problems, where probabilistic knowledge is exchanged between two Bayesian network-based probabilistic databases relative to their underlying deterministic ontologies, and the deterministic and probabilistic mapping between the two ontologies is defined via deterministic and probabilistic existential mapping rules, respectively. − We provide an in-depth analysis of the data and combined complexity of deciding the existence of probabilistic (universal) solutions and obtain a (fairly) complete picture of the data complexity, general combined complexity, bounded-arity (ba) combined, and fixed-program combined (fp) complexity for the main sublanguages of the Datalog+/– family. We also delineate some tractable special cases, and provide complexity results for exact UCQ (union of conjunctive queries) answering. − For the complexity analysis, we consider a compact encoding of probabilistic source databases and mappings, which is used in the area of both incomplete and probabilistic databases, and also known as data provenance or data lineage [ 14, 12, 13, 22 ]. Here, we consider data provenance for probabilistic data that is structured according to an underlying Bayesian network. 2

Preliminaries We assume infinite sets of constants C, (labeled) nulls N, and regular variables V. A term t is a constant, null, or variable. An atom has the form p(t1, . . . , tn), where p is an n-ary predicate, and t1, . . . , tn are terms. Conjunctions of atoms are often identified with the sets of their atoms. An instance I is a (possibly infinite) set of atoms p(t), where t is a tuple of constants and nulls. A database D is a finite instance that contains only constants. A homomorphism is a substitution h : C ∪ N ∪ V → C ∪ N ∪ V that is the identity on C. We assume familiarity with conjunctive queries (CQs). The answer to a CQ q over an instance I is denoted q(I). A Boolean CQ (BCQ) q evaluates to true over I, denoted I |= q, if q(I) 6= ∅.

A tuple-generating dependency (TGD) σ is a first-order formula ∀X ϕ(X) → ∃Y p(X, Y), where X ∪ Y ⊆ V, ϕ(X) is a conjunction of atoms, and p(X, Y) is an atom. We call ϕ(X) the body of σ, denoted body (σ), and p(X, Y) the head of σ, denoted head (σ). We consider only TGDs with a single atom in the head, but our results can be extended to TGDs with a conjunction of atoms in the head. An instance I satisfies σ, written I |= σ, if the following holds: whenever there exists a homomorphism h such that h(ϕ(X)) ⊆ I, then there exists h0 ⊇ h|X, where h|X is the restriction of h to X, such that h0(p(X, Y)) ∈ I. A negative constraint (NC) ν is a first-order formula ∀X ϕ(X) → ⊥, where X ⊆ V, ϕ(X) is a conjunction of atoms, called the body of ν, denoted body (ν), and ⊥ denotes the truth constant false. An instance I satisfies ν, denoted I |= ν, if there is no homomorphism h such that h(ϕ(X)) ⊆ I. Given a set Σ of TGDs and NCs, I satisfies Σ, denoted I |= Σ, if I satisfies each TGD and NC of Σ. For brevity, we omit the universal quantifiers in front of TGDs and NCs.

Given a database D and a set Σ of TGDs and NCs, the answers that we consider are those that are true in all models of D and Σ. Formally, the models of D and Σ, denoted mods(D, Σ), is the set of instances {I | I ⊇ D and I |= Σ}. The answer to a CQ q relative to D and Σ is defined as the set of tuplesans(q, D, Σ) = TI∈mods(D,Σ){t | t ∈ q(I)}. The answer to a BCQ q is true, denoted D ∪ Σ |= q, if ans(q, D, Σ) 6= ∅. The problem of CQ answering is defined as follows: given a database D, a set Σ of TGDs and NCs, a CQ q, and a tuple of constants t, decide whether t ∈ ans(q, D, Σ). Following Vardi’s taxonomy [ 23 ], the combined complexity of BCQ answering is calculated by considering all the components, i.e., the database, the set of dependencies, and the query, as part of the input. The bounded-arity combined complexity (or simply ba-combined complexity) is calculated by assuming that the arity of the underlying schema is bounded by an integer constant. Notice that in the context of description logics (DLs), whenever we refer to the combined complexity in fact we refer to the ba-combined complexity since, by definition, the arity of the underlying schema is at most two. The fixed-program combined complexity (or simply fp-combined complexity) is calculated by considering the set of TGDs and NCs as fixed. 3 In this section, we define the notions ofdeterministic and probabilistic ontological data exchange. The source (resp., target) of the deterministic/probabilistic ontological data exchange problems that we consider in this paper is a probabilistic database (resp., probabilistic instance), each relative to a deterministic ontology. Here, a probabilistic database (resp., probabilistic instance) over a schema S is a probability space P r = (I, μ) such that I is the set of all (possibly infinitely many) databases (resp., instances) over S, and μ : I → [ 0, 1 ] is a function that satisfiesPI∈I μ(I) = 1. 3.1 Ontological data exchange formalizes data exchange from a probabilistic database relative to a source ontology Σs (consisting of TGDs and NCs) over a schema S to a probabilistic target instance Prt relative to a target ontology Σt (consisting of a set of TGDs and NCs) over a schema T via a (source-to-target) mapping (also consisting of a set of TGDs and NCs). More specifically, anontological data exchange (ODE) problem M= (S, T, Σs, Σt, Σst) consists of (i) a source schema S, (ii) a target schema T disjoint from S, (iii) a finite setΣs of TGDs and NCs over S (called source ontology), (iv) a finite set Σt of TGDs and NCs over T (called target ontology), and (v) a finite setΣst of TGDs and NCs σ over S ∪ T (called (source-to-target) mapping) such that body(σ) and head(σ) are defined overS ∪ T and T, respectively.

Ontological data exchange with deterministic databases is based on defining a target instance J over T as being a solution for a deterministic source database I over S relative to an ODE problem M = (S, T, Σs, Σt, Σst), if (I ∪ J ) |= Σs ∪ Σt ∪ Σst. We denote by SolM the set of all such pairs (I, J ). Among the possible deterministic solutions J to a deterministic source database I relative to M in SolM, we prefer universal solutions, which are the most general ones carrying only the necessary information for data exchange, i.e., those that transfer only the source database along with the relevant implicit derivations via Σs to the target ontology. A universal solution can be homomorphically mapped to all other solutions leaving the constants unchanged. Hence, a deterministic target instance J over S is a universal solution for a deterministic source database I over T relative to a schema mapping M, if (i) J is a solution, and (ii) for each solution J 0 for I relative to M, there is a homomorphism h : J → J 0. We denote by USol M (⊆ SolM) the set of all pairs (I, J ) of deterministic source databases I and target instances J such that J is a universal solution for I relative to M.

When considering probabilistic databases and instances, a joint probability space Pr over the solution relation SolM and the universal solution relation USolM must exist. More specifically, a probabilistic target instancePrt = (J , μt) is a probabilistic solution (resp., probabilistic universal solution) for a probabilistic source database Prs = (I, μs) relative to an ODE problem M = (S, T, Σs, Σt, Σst), if there exists a probability space Pr = (I × J , μ) such that (i) the left and right marginals of Pr are Prs and Prt, respectively, i.e., (i.a) μs(I) = PJ∈J μ(I, J ) for all I ∈ I, (i.b) μt(J ) = P μ(I, J ) for all J ∈ J ; and (ii) μ(I, J ) = 0 for all (I, J ) 6∈ SolM (resp., (I, J ) 6∈ USoIl∈MI ). Note that this intuitively says that all non-solutions (I, J ) have probability zero and the existence of a solution does not exclude that some source databases with probability zero have no corresponding target instance.

Example 1. An ontological data exchange (ODE) problem M = (S, T, Σs, Σt, Σst) is given by the source schema S = {Researcher/2, ResearchArea/2, Publication/3} (the number after each predicate denotes its arity), the target schema T = {UResearchArea/3, Lecturer/2}, the source ontology Σs = {σs, νs}, the target ontology Σt = {σt, νt}, and the mapping Σst = {σst, νm}, where: σs : Publication(X, Y, Z) → ResearchArea(X, Y), νs : Researcher(X, Y) ∧ ResearchArea(X, Y) → ⊥, σt : UResearchArea(U, D, T) → ∃Z Lecturer(T, Z), νt : Lecturer(X, Y) ∧ Lecturer(Y, X) → ⊥,

Possible source database facts ra Researcher(Alice, UnivOx) rp Researcher(Paul, UnivOx) paml Publication(Alice, ML, JMLR) padb Publication(Alice, DB, TODS) ppdb Publication(Paul, DB, TODS) ppai Publication(Paul, AI, AIJ) Probabilistic source database Prs = (I, μs) I1 = {ra,rp,paml,ppdb,aaml,apdb} 0.5 I2 = {ra,rp,paml,ppai,aaml,apai} 0.2 I3 = {ra,rp,padb,ppai,aadb,apai} 0.15 I4 = {ra,rp,padb,ppdb,aadb,apdb} 0.075 I5 = {ra,padb,aadb} 0.075

Derived source database facts aaml ResearchArea(Alice, ML) aadb ResearchArea(Alice, DB) apdb ResearchArea(Paul, DB) apai ResearchArea(Paul, AI)

Possible target instance facts uml UResearchArea(UnivOx, N1, ML) uai UResearchArea(UnivOx, N2, AI) udb UResearchArea(UnivOx, N3, DB) lml Lecturer(ML, N4) lai Lecturer(AI, N5) ldb Lecturer(DB, N6) Probabilistic target instance Prt1 = (J1, μt1 ) Probabilistic target instance Prt2 = (J2, μt2 ) JJJ213 === {{{uuuammill,,,uuudadbib,,,lllammil,l,l,ldladbib}}} 000...2515 JJ56 == {{uummll,,uudaib,,llmmll,,lladib}} 00..515

J4 = {udb,ldb} 0.15 J7 = {uml,uai,udb,lml,lai,ldb} 0.35 (N1, . . . , N6 are nulls); both are probabilistic solutions, but only Prt1 is universal.

Fig. 1. Probabilistic universal solution Prt1 .

Fig. 2. Probabilistic solution Prt2 . νst : ResearchArea(N, T) ∧ UResearchArea(U, T, N) → ⊥.

σst : ResearchArea(N, T) ∧ Researcher(N, U) → ∃D UResearchArea(U, D, T), Given the probabilistic source database in Table 1, two probabilistic instances Prt1 = (J1, μt1 ) and Prt2 = (J2, μt2 ) that are probabilistic solutions are shown in Table 1. Note that only Prt1 is also a probabilistic universal solution. Note also that Figures 1 and 2 show the probability spaces over Prt1 and Prt2 , respectively.

Query answering in ontological data exchange is performed over the target ontology and is generalized from deterministic data exchange. A union of conjunctive queries (or UCQ) has the form q(X) = Wk

i=1 ∃Yi Φi(X, Yi, Ci), where each ∃Yi Φi(X, Yi, Ci) with i ∈ {1, . . . , k} is a CQ with exactly the variables X and Yi, and the constants Ci. Given an ODE problem M = (S, T, Σs, Σt, Σst), probabilistic source database Prs = (I, μs), UCQ q(X) = Wk

i=1 ∃Yi Φi(X, Yi, Ci), and tuple t (a ground instance of X in q) over C, the confidence of t relative to q, denoted conf q(t), in Prs relative to M is the infimum ofPrt(q(t)) subject to all probabilistic solutions Prt for Prs relative to M. Here, Prt(q(t)) for Prt = (J , μt) is the sum of all μt(J ) such that q(t) evaluates to true in the instance J ∈ J (i.e., some BCQ ∃Yi Φi(t, Yi, Ci) with i ∈ {1, . . . , k} evaluates to true in J ).

Example 2. Consider again the setting of Example 1, and let q be a UCQ of a student who wants to know whether she can study either machine learning or artificial intelligence at the University of Oxford: q() = ∃X, Z(Lecturer(AI, X) ∧ UResearchArea(UnivOx, Z, AI)) ∨ ∃X, Z(Lecturer(ML, X) ∧ UResearchArea(UnivOx, Z, ML)). Then, q yields the probabilities 0.85 and 1 on Prt1 and Prt2 , respectively. Probabilistic ontological data exchange extends deterministic ontological data exchange by turning the deterministic source-to-target mapping into a probabilistic source-totarget mapping, i.e., we have a probability distribution over the set of all subsets of Σst. More specifically, a probabilistic ontological data exchange (PODE) problem M = (S, T, Σs, Σt, Σst, μst) consists of (i) a source schema S, (ii) a target schema T disjoint from S, (iii) a finite set Σs of TGDs and NCs over S (called source ontology), (iv) a finite set Σt of TGDs and NCs over T (called target ontology), (v) a finite set Σst of TGDs and NCs σ over S ∪ T, and (vi) a function μst : 2Σst → [ 0, 1 ] such that PΣ0⊆Σst μst(Σ0) = 1 (called probabilistic (source-to-target) mapping).

A probabilistic target instance Prt = (J , μt) is a probabilistic solution (resp., probabilistic universal solution) for a probabilistic source database Prs = (I, μs) relative to a PODE problem M = (S, T, Σs, Σt, Σst, μst), if there exists a probability space Pr = = (I ×J ×2Σst , μ) such that: (i) the three marginals of μ are μs, μt, and μst, such that: (i.a) μs(I) = PJ∈J , Σ0⊆Σst μ(I, J, Σ0) for all I ∈ I, (i.b) μt(J ) = PI∈I, Σ0⊆Σst μ(I, J, Σ0) for all J ∈ J , and (i.c) μst(Σ0) = PI∈I, J∈J μ(I, J, Σ0) for all Σ0 ⊆ Σst; and (ii) μ(I, J, Σ0) = 0 for all (I, J ) 6∈ Sol (S,T,Σ0) (resp., (I, J ) 6∈ USol (S,T,Σ0)).

Using probabilistic (universal) solutions for probabilistic source databases relative to PODE problems, the semantics of UCQs is lifted to PODE problems as follows. Given a PODE problem M = (S, T, Σs, Σt, Σst, μst), a probabilistic source database Prs = (I, μs), a UCQ q(X) = Wik=1 ∃Yi Φi(X, Yi, Ci), and a tuple t (a ground instance of X in q) over C, the confidence of t relative to q, denoted conf q(t), in Prs relative to M is the infimum ofPrt(q(t)) subject to all probabilistic solutions Prt for Prs relative to M. Here, Prt(q(t)) for Prt = (J , μt) is the sum of all μt(J ) such that q(t) evaluates to true in the instance J ∈ J . We use a compact encoding of both probabilistic databases and probabilistic mappings, which is based on annotating facts, TGDs, and NCs by probabilistic events in a Bayesian network, rather than explicitly specifying the whole probability space.

We first define annotations and annotated atoms. Lete1, . . . , en be n ≥ 1 elementary events. A world w is a conjunction `1 ∧· · ·∧`n, where each `i, i ∈ {1, . . . , n}, is either the elementary event ei or its negation ¬ei. An annotation λ is any Boolean combination of elementary events (i.e., all elementary events are annotations, and if λ1 and λ2

Possible source database facts Annotation ra Researcher(Alice, UnivOx) true rp Researcher(Paul, UnivOx) e1∨ e2∨ e3∨ e4 paml Publication(Alice, ML, JMLR) e1∨ e2 padb Publication(Alice, DB, TODS) ¬ e1 ∧ ¬ e2 ppdb Publication(Paul, DB, TODS) e1∨ (¬ e2 ∧ ¬ e3∧ e4) ppai Publication(Paul, AI, AIJ) (¬ e1∧ e2) ∨ (¬ e1∧ e3) are annotations, then also ¬λ1 and λ1 ∧ λ2). An annotated atom has the form a : λ, where a is an atom, and λ is an annotation.

The compact encoding of probabilistic databases can then be defined as follows. Note that this encoding is also underlying our complexity analysis in Section 4. A set A of annotated atoms along with a probability μ(w) ∈ [ 0, 1 ] for every world w compactly encodes a probabilistic database P r = (I, μ) whenever: (i) the probability μ of every annotation λ is the sum of the probabilities of all worlds in which λ is true, and (ii) the probability μ of every subset-maximal database {a1, . . . , am} ∈ I 4 such that {a1 : λ1, . . . , am : λm} ⊆ A for some annotations λ1, . . . , λm is the probability μ of λ1 ∧ · · · ∧ λm (and the probability μ of every other database in I is 0).

We assume that the probability distributions for the underlying events are given by a Bayesian network, which is usually used for compactly specifying a joint probability space, encoding also a certain causal structure between the variables. The following example in Tables 2 and 3 illustrates the compact encoding of probabilistic source databases via Boolean annotations relative to an underlying Bayesian network.

If the mapping is probabilistic as well, then we use two disjoint sets of elementary events, one for encoding the probabilistic source database and the other one for the mapping. In this way, the probabilistic source database is independent from the probabilistic mapping. We now define the compact encoding of probabilistic mappings. An annotated TGD (resp., NC) has the form σ : λ, where σ is a TGD (resp., NC), and λ is an annotation. A set Σ of annotated TGDs and NCs σ : λ with σ ∈ Σst along with a probability μ(w) ∈ [ 0, 1 ] for every world w compactly encodes a probabilistic mappings μst : 2Σst → [ 0, 1 ] whenever (i) the probability μ of every annotation λ is the sum of the probabilities of all worlds in which λ is true, and (ii) the probability μst of every 4 That is, we do not consider subsets of the databases here. subset-maximal {σ1, . . . , σk} ⊆ Σst such that {σ1 : λ1, . . . , σk : λk} ⊆ Σ for some annotations λ1, . . . , λk is the probability μ of λ1 ∧ · · · ∧ λk (and the probability μst of every other subset of Σst is 0). 3.4 We consider the following computational problems: Existence of a solution (resp., universal solution): Given an ODE or a PODE problem M and a probabilistic source database Prs, decide whether there exists a probabilistic (resp., probabilistic universal) solution for Prs relative to M.

Answering UCQs: Given an ODE or a PODE problem M, a probabilistic source database Prs, a UCQ q(X), and a tuple t over C, compute conf Q(t) in Prs w.r.t. M. 4 We now analyze the computational complexity of deciding the existence of a (universal) probabilistic solution for deterministic and probabilistic ontological data exchange problems. We also delineate some tractable special cases, and we provide some complexity results for exact UCQ answering for ODE and PODE problems.

We assume some elementary background in complexity theory [ 15, 20 ]. We now briefly recall the complexity classes that we encounter in our complexity results. The complexity classes PSPACE (resp., P, EXP, 2EXP) contain all decision problems that can be solved in polynomial space (resp., polynomial, exponential, double exponential time) on a deterministic Turing machine, while the complexity classes NP and NEXP contain all decision problems that can be solved in polynomial and exponential time on a nondeterministic Turing machine, respectively; coNP and coNEXP are their complementary classes, where “Yes” and “No” instances are interchanged. The complexity class AC0 is the class of all languages that are decidable by uniform families of Boolean circuits of polynomial size and constant depth. The inclusion relationships among the above (decision) complexity classes (all currently believed to be strict) are as follows:

AC0 ⊆ P ⊆ NP, coNP ⊆ PSPACE ⊆ EXP ⊆ NEXP, coNEXP ⊆ 2EXP

The (function) complexity class #P is the set of all functions that are computable by a polynomial-time nondeterministic Turing machine whose output for a given input string I is the number of accepting computations for I. The main (syntactic) conditions on TGDs that guarantee the decidability of CQ answering are guardedness [ 6 ], stickiness [ 8 ], and acyclicity. Each one of these conditions has its “weak” counterpart: weak guardedness [ 6 ], weak stickiness [ 8 ], and weak acyclicity [ 11 ], respectively.

A TGD σ is guarded if there exists an atom in its body that contains (or “guards”) all the body variables of σ. The class of guarded TGDs, denoted G, is defined as the

Data Comb. ba-comb. fp-comb.

L, LF, AF in AC0 PSPACE

G P 2EXP WG EXP 2EXP S, SF in AC0 EXP F, GF P EXP

A in AC0 NEXP WS, WA P 2EXP

NP EXP EXP NP NP NEXP 2EXP

NP NP EXP NP NP NP NP

Data Comb. ba-comb. fp-comb.

L, LF, AF coNP PSPACE coNP coNP

G coNP 2EXP EXP coNP WG EXP 2EXP EXP EXP S, SF coNP EXP coNP coNP F, GF coNP EXP coNP coNP

A coNP coNEXP coNEXP coNP WS, WA coNP 2EXP 2EXP coNP Fig. 3. Complexity of BCQ answering [ 18 ].

All entries except for “in AC0” are completeness ones, where hardness in all cases holds even for ground atomic BCQs.

Fig. 4. Complexity of existence of a probabilistic (universal) solution (for both deterministic and probabilistic ODE). All entries are completeness results. family of all possible sets of guarded TGDs. A key subclass of guarded TGDs are the so-called linear TGDs with just one body atom (which is automatically a guard), and the corresponding class is denoted L. Weakly guarded TGDs extend guarded TGDs by requiring only “harmful” body variables to appear in the guard, and the associated class is denoted WG. It is easy to verify that L ⊂ G ⊂ WG.

Stickiness is inherently different from guardedness, and its central property can be described as follows: variables that appear more than once in a body (i.e., join variables) are always propagated (or “stick”) to the inferred atoms. A set of TGDs that enjoys the above property is called sticky, and the corresponding class is denoted S. Weak stickiness is a relaxation of stickiness where only “harmful” variables are taken into account. A set of TGDs which enjoys weak stickiness is weakly sticky, and the associated class is denoted WS. Observe that S ⊂ WS.

A set Σ of TGDs is acyclic if its predicate graph is acyclic, and the underlying class is denoted A. In fact, an acyclic set of TGDs can be seen as a nonrecursive set of TGDs. We say Σ is weakly acyclic if its dependency graph enjoys a certain acyclicity condition, which actually guarantees the existence of a finite canonical model; the associated class is denoted WA. Clearly, A ⊂ WA.

Another key fragment of TGDs, which deserves our attention, are the so-called full TGDs, i.e., TGDs without existentially quantified variables, and the corresponding class is denoted F. If we further assume that full TGDs enjoy linearity, guardedness, stickiness, or acyclicity, then we obtain the classes LF, GF, SF, and AF, respectively.

Overview of Complexity Results Our complexity results for deciding the existence of a probabilistic (universal) solution for both ODE and PODE problems with annotations over events relative to an underlying Bayesian network are summarized in Fig. 4 for all classes of existential rules discussed above in the data, combined, ba-combined, and fp-combined complexity (all entries are completeness results). For L, LF, AF, S, SF, and A in the data complexity, we obtain tractability when the underlying Bayesian network is a polytree. For all other cases, hardness holds even when the underlying Bayesian network is a polytree. Finally, for all classes of existential rules discussed above except for WG, answering UCQs for both ODE and PODE problems is in #P in the data complexity. 4.3 The first result shows that deciding whether there exists a probabilistic (or probabilistic universal) solution for a probabilistic source database relative to an ODE problem is complete for C (resp., coC), if BCQ answering for the involved sets of TGDs and NCs is complete for a deterministic (resp., nondeterministic) complexity class C ⊇ PSPACE (resp., C ⊇ NP), and hardness holds even for ground atomic BCQs. As a corollary, by the complexity of BCQ answering with TGDs and NCs in Figure 3 [ 18 ], we immediately obtain the complexity results shown in Figure 4 for deciding the existence of a probabilistic (universal) solution (in deterministic ontological data exchange) in the combined, ba-combined, and fp-combined complexity, and for the class WG of TGDs and NCs in the data complexity. The hardness results hold even when the underlying Bayesian network is a polytree.

Theorem 1. Given a probabilistic source database P rs relative to a source ontology Σs and an ODE problem M = (S, T, Σs, Σt, Σst) such that Σs ∪ Σt ∪ Σst belongs to a class of TGDs and NCs for which BCQ answering is complete for a deterministic (resp., nondeterministic) complexity class C ⊇ PSPACE (resp., C ⊇ NP), and hardness holds even for ground atomic BCQs, deciding the existence of a probabilistic (universal) solution for P rs relative to Σs and M is complete for C (resp., coC). Hardness holds even when the underlying Bayesian network is a polytree.

The following result shows that deciding whether there exists a probabilistic (universal) solution for a probabilistic source database relative to an ODE problem is complete for coNP in the data complexity, for all classes of sets of TGDs and NCs considered in this paper, except for WG. Hardness for coNP for the classes G, F, GF, WS, and WA holds even when the underlying Bayesian network is a polytree.

Theorem 2. Given a probabilistic source database P rs relative to a source ontology Σs and an ODE problem M = (S, T, Σs, Σt, Σst) such that Σs ∪ Σt ∪ Σst belongs to a class among L, LF, AF, G, S, SF, F, GF, A, WS, and WA, deciding whether there exists a probabilistic (or probabilistic universal) solution for P rs relative to Σs and M is coNP-complete in the data complexity. Hardness for coNP for the classes G, F, GF, WS, and WA holds even when the underlying Bayesian network is a polytree.

The following result shows that deciding whether there exists a probabilistic (or probabilistic universal) solution for a probabilistic source database relative to an ODE problem is in P in the data complexity, if BCQ answering for the involved sets of TGDs and NCs is first-order rewritable as a Boolean UCQ, and the underlying Bayesian network is a polytree. As a corollary, by the complexity of BCQ answering with TGDs and NCs, deciding the existence of a solution is in P for the classes L, LF, AF, S, SF, and A in the data complexity, if the underlying Bayesian network is a polytree. Theorem 3. Given a probabilistic source database P rs relative to a source ontology Σs, with a polytree as Bayesian network, and an ODE problem M = (S, T, Σs, Σt, Σst) such that Σs ∪ Σt ∪ Σst belongs to a class of TGDs and NCs for which BCQ answering is first-order rewritable as a Boolean UCQ, deciding whether there exists a probabilistic (universal) solution for P rs relative to Σs and M is in P in the data complexity.

Finally, the following theorem shows that answering UCQs for probabilistic source databases relative to an ODE problem is complete for #P in the data complexity for all above classes of existential rules except for WG.

Theorem 4. Given (i) an ODE problem M = (S, T, Σt, Σs, Σst) such that Σs ∪ Σst ∪ Σt belongs to a class among L, LF, AF, G, S, SF, F, GF, A, WS, and WA, and (ii) a probabilistic source database P rs relative to Σs such that there exists a solution for P rs relative to M, (iii) a UCQ Q = q(X) over T, and (iv) a tuple a, computing confQ(a) is #P-complete in the data complexity. All the results of Section 4.3 in Theorems 1 and 4 carry over to the case of probabilistic ontological data exchange. Clearly, the hardness results carry over immediately, since deterministic ontological data exchange is a special case of probabilistic ontological data exchange. As for the membership results, we additionally consider the worlds for the probabilistic mapping, which are iterated through in the data complexity and guessed in the combined, the ba-combined, and the fp-combined complexity. 5

Summary and Outlook We have defined deterministic and probabilistic ontological data exchange problems, where probabilistic knowledge is exchanged between two ontologies. The two ontologies and the mapping between them are defined via existential rules, where the rules for the mapping are deterministic and probabilistic, respectively. We have given a precise analysis of the computational complexity of deciding the existence of a probabilistic (universal) solution for different classes of existential rules in both deterministic and probabilistic ontological data exchange. We also have delineated some tractable special cases, and we have provided some complexity results for exact UCQ answering.

An interesting topic for future research is to further explore the tractable cases of probabilistic solution existence and whether they can be extended, e.g., by slightly generalizing the type of the mapping rules. Another issue for future work is to further analyze the complexity of answering UCQs for different classes of existential rules in deterministic and probabilistic ontological data exchange.

Acknowledgments. This work was supported by an EU (FP7/2007-2013) Marie-Curie Intra-European Fellowship (“PRODIMA”), the UK EPSRC grant EP/J008346/1 (“PrOQAW”), the ERC grant 246858 (“DIADEM”), a Yahoo! Research Fellowship, and funds from Universidad Nacional del Sur and CONICET, Argentina. This paper is a short version of a paper that appeared in Proc. RuleML 2015 [ 19 ].

Refining Software Quality Prediction with LOD

Davide Ceolin1, Till D¨ohmen1, and Joost Visser2

1 VU University Amsterdam

de Boelelaan 1081 1081HV Amsterdam, The Netherlands

[e-mail] 2 Software Improvement Group Rembrandt Toren, 15th floor, Amstelplein 1

1096 HA Amsterdam, The Netherlands Abstract. The complexity of software systems is growing and the computation of several software quality metrics is challenging. Therefore, being able to use the already estimated quality metrics to predict their evolution is a crucial task. In this paper, we outline our idea to use Linked Open Data to enrich the information available for such prediction. We report our experience so far, and we outline the preliminary results obtained. 1 Software size and complexity is growing, thus being able to estimate and predict software quality is crucial to monitor the process of software development and promptly steer it. In fact, a quality metric provides a value summarizing one relevant aspect of the software that can be consulted to identify issues or risks in the development process or in the software itself. Therefore, several different quality dimensions have been defined, as described, for instance, by Kan [ 8 ].

Estimating software quality is then a crucial but challenging task, for several reasons including the complexity of the software to be measured and the fact that these measures are often hard to quantify: some of them depend on runtime software behavior, some on static software properties. The estimation of the values of these measures is possible, as demonstrated, for instance, by Alves and Visser [ 2 ] and Bouwers [ 4 ]. However, given the complexity of this task, we propose to use such estimates to predict the temporal evolution of these values.

Preliminary analyses on a dataset from the Software Improvement Group3 show encouraging results on the use of these estimates as starting point for the prediction of the evolution over time of software quality ratings.4 We hypothesize that, by using Linked Open Data (LOD) we can improve and refine the accuracy of our predictions. In particular, by enriching the information available about the projects analyzed, we can categorize these projects (e.g., by industry sector or programming language), thus increasing the possibility to group 3 http://www.sig.eu 4 For confidentiality reasons, we could not make the dataset publicly available. together projects showing similar quality evolution over time. We present here some preliminary encouraging results obtained in this direction, and we discuss a series of open issues that we need to address in order to extend this research.

The rest of this paper is structured as follows: Section 2 introduces related work. Section 3 describes the enrichment of software projects data. Section 4 provides preliminary results, that are discussed in Section 5. 2 Software quality prediction is an important issue, that has been tackled from different points of view. As Al-Jamini and Ahmed [ 1 ] describe in their review, several relevant approaches to this problem make use of machine learning.

We have also employed machine learning techniques (in particular, Markov chains [ 12 ]) to predict software quality based on the starting rating of a project [ 5 ]. The results are promising and we will aim at perfecting them with additional features, properly selected from external sources, like LOD. The future quality value of systems shows a strong correlation with the current quality rating, due to the fact that the rating usually changes very slowly over time. Moreover, a second trend was discovered which revealed that higher quality systems tend to deteriorate in quality and low-quality systems tend to improve, both with the tendency towards the medium quality level. This could be explained as a case of regression towards the mean [ 6 ], i.e., could be due to noise in the extreme quality ratings that disappears as more accurate estimates are provided. However, this possible explanation still needs to be evaluated and, anyway, could explain only the second trend. These two trends, for very high or very low-quality systems, yield a high uncertainty in the prediction. Using LOD, we expect to obtain more tailored predictions (e.g., by identifying software quality trends associated to the programming language adopted) to reduce prediction uncertainty.

Misirli et al.[ 11 ] propose the use of Bayesian Networks to make software quality predictions. As the number of potentially useful features grows (consequently to LOD enrichment), we will consider this approach in the future. Jing et al. [ 7 ] use a dictionary learning-approach that represents a more specialized but limited approach as compared to our use of LOD.

Enriching Software Quality Prediction with LOD Our hypothesis is that by enriching the information about the projects we analyze with LOD, we can obtain features that are useful for improving the software quality prediction. For instance, software quality could vary in different industrial sectors or the programming language used could affect quality evolution.

Our focus is on a dataset provided by the Software Improvement Group, which consists mainly of projects of Dutch companies and of a few additional European customers. We enriched the dataset using mainly DBpedia [ 3 ]. In the enrichment process, we encountered the following issues: Missing information DBpedia contains a description of only 209 companies located in the Netherlands. Additional companies have been identified in the Dutch DBpedia5, which contains the description of 3.883 companies, but does not provide information about their location.

Disambiguation Some companies have homonyms. To disambiguate resources and identify the right URI for a given company, we expect to employ heuristics based on the company website, its location, and industry sector. Consistency literals vs. URIs Some classifications are available in an inconsistent manner. For instance, industry can appear both as http://dbpedia. org/ontology/industry and http://dbpedia.org/property/industry. In some cases, the value of one of these two properties is reported only as a literal value, thus affecting the possibility to perform ontological reasoning. We performed a preliminary analysis on a dataset consisting of 1019 snapshots of maintainability of 112 companies. These snapshots already presented a first industry classification provided by SIG. In total, 14 industrial sectors are present.

We computed the semantic similarity between each possible combination of industrial categories using the Wikipedia distance [ 10 ] and the WU & Palmer distance [ 17 ]. On these data, we performed a series of preliminary analyses: 1. We run a Wilcoxon signed-rank test [ 16 ] at 95% confidence level to check if the observations are significantly different when grouped per industrial sector. These results show a weak positive Spearman [ 15 ] correlation with both the Wikipedia (0.07) and the Wu & Palmer (0.14) distances. 2. We computed the same procedure as above by using also the KolmogorovSmirnov test [ 9, 14 ] . This resulted in a slightly higher correlation, 0.16 for the Wikipedia distance and 0.24 for the Wu & Palmer distance. 3. We computed the contrast analysis [ 13 ] of the linear combinations of the observations, again grouped per industrial sector. The resulting contrast estimators showed a weak correlation with the Wikipedia distance (0.15) and with the Wu & Palmer distance values (0.12). 4. We grouped a small set of observations aligned with DBpedia by industrial sector of the companies involved (telecommunication and financial services). According to a Wilcoxon signed-rank test at 90% significance, the two groups are significantly different, according to the Kolmogorov-Smirnov test, not. 5

Discussion and Future Work We present an early stage work about the use of LOD to refine the precision and accuracy of software quality prediction. We performed a series of exploratory and preliminary studies which shows a low correlation between the maintainability and the industry sector of these projects. These results provide the basis for further exploration because: (1) the existence of a weak correlation is confirmed by more tests, hence it is possible that we can identify a subset of the data analyzed that presents a higher correlation; (2) the different methods for computing semantic similarity and different statistical significance tests provided significantly different results, thus indicating the need for exploring different computational techniques; (3) as shown by the last item of Section 4, the industrial sector seems to be a discriminant for software quality, although this aspect needs to be evaluated on larger datasets; and (5) our analyses focused on a limited set of enrichment features, but several others are utilizable. So, we plan to extend this research to identify the most robust methods to perform these predictions, and we will extend these analyses including additional LOD features and sources. Acknowledgements This work is funded by Amsterdam Data Science. References

Reducing the Size of the Optimization Problems in Fuzzy Ontology Reasoning

Fernando Bobillo1 and Umberto Straccia2

1 Dpt. of Computer Science & Systems Engineering, University of Zaragoza, Spain 2 Istituto di Scienza e Tecnologie dell’Informazione (ISTI - CNR), Pisa, Italy

Email: [e-mail], [e-mail] Abstract. Fuzzy ontologies allow the representation of imprecise structured knowledge, typical in many real-world application domains. A key factor in the practical success of fuzzy ontologies is the availability of highly optimized reasoners. This short paper discusses a novel optimization technique: a reduction of the size of the optimization problems obtained during the inference by the fuzzy ontology reasoner fuzzyDL. 1 In recent years, we have noticed an increase in the number of applications for mobile devices that could benefit from the use of semantic reasoning services [ 1 ]. Because of the limited capabilities of mobile devices, it is especially important to develop reasoning algorithms performing efficiently in practice. In order to deal with imprecise knowledge, such applications could use fuzzy ontologies [ 8 ]. In fuzzy ontologies, concepts and relations are fuzzy. Consequently, the axioms are not in general either true or false, but they may hold to some degree of truth.

However, little effort has been paid so far to the study and implementation of optimization techniques for fuzzy ontology reasoning, which is essential to reason with real-world scenarios in practice (some exceptions are [ 3,4,5,6 ]). This short paper discusses some optimization techniques to improve the performance of the reasoning algorithm by reducing the size of optimization problems obtained during the inference. In particular, we will provide optimized MILP encodings of the restrictions involving n-ary operators and fuzzy membership functions. Such optimizations have been implemented in fuzzyDL, arguably the most popular and advanced fuzzy ontology reasoner [ 2 ], and proved their usefulness. 2

Background on fuzzyDL reasoning We assume the reader to be familiar with the syntax and semantics of fuzzy Description Logics (DLs) [ 8 ]. The reasoning algorithm implemented in fuzzyDL combines tableaux rules with an optimization problem. After some preprocessing, fuzzyDL applies tableau rules decomposing complex concept expressions into simpler ones, as usual in tableau algorithms, but also generating a system of inequation constraints. These inequations have to hold in order to respect the semantics of the DL constructors. After all rules have been applied, an optimization problem must be solved before obtaining the final solution. The tableau rules are deterministic and the optimization problem is unique.

This optimization problem has a solution iff the fuzzy KB is consistent. In fuzzyDL, we obtain a bounded Mixed Integer Linear Programming [ 7 ] (MILP) problem, that is, minimising a linear function with respect to a set of constraints that are linear inequations in which rational and integer variables can occur. The problem is bounded, with rational variables ranging over [ 0, 1 ] and some integer variables ranging over {0, 1}. For example, in Lukasiewicz fuzzy DLs, the restriction x1 ⊗L x2 = z can be encoded using the set of constraints {x1 +x2 −1 ≤ z, x1 + x2 − 1 ≥ z − y, z ≤ 1 − y, y ∈ {0, 1}}. Observe that the MILP encoding of the restriction has introduced a new variable y: the two possibilities y = 0 and y = 1 encode the non-deterministic choice implicit in the interpretation of the conjunction under Lukasiewicz fuzzy logic. The complexity of solving a MILP problem is NP-complete and it depends on the number of variables, so it is convenient to reduce the number of new variables.

Let x, z be [ 0, 1 ]-variables, and xu be a rational unbounded variable. fuzzyDL has to solve some restrictions involving fuzzy connectives, such as x1 = x2, x1 ⊗ x2 = z, x1 ⊕ x2 = z, or x1 ⇒ x2 = z. Furthermore, it also needs to solve some restrictions d(xu) ≥ z involving fuzzy membership functions d such as the trapezoidal(k1, k2, q1, q2, q3, q4) (see Table 1 (a)), the triangular(k1, k2, q1, q2, q3), lef t(k1, k2, q1, q2), or right(k1, k2, q1, q2) [ 8 ]. Let us start with the case of conjunction concepts in Lukasiewicz fuzzy DLs. An n-ary concept of the form (C1 u C2 u · · · u Cn) can be represented, using associativity, only using binary conjunctions (C1 u(C2 u(· · ·uCn)) . . . ). A binary conjunction concept introduces a restriction of the form x1 ⊗L x2 = z which, as shown in Section 2, can be encoded adding a new binary variable y. Hence, in order to represent the n-ary conjunction, n − 1 new variables yi would be needed. However, it is possible to give a more efficient representation by considering the conjunction as an n-ary operator. Indeed, a restriction of the form x1 ⊗L x2 ⊗ · · · ⊗ xn = z can be encoded using only one new binary variable and, thus, saves 2n−2 possible alternative assignments to the variables yi.

n X xi − (n − 1) ≤ z, i=1

y ≤ 1 − z, n X xi − (n − 1) ≥ z − (n − 1)y, i=1

y ∈ {0, 1}. y = 0 encodes the case z = Pn

i=1 xi − (n − 1) ≥ 0, and y = 1 encodes the case z = 0 and Pn

i=1 xi − (n − 1) < 0. Let us consider now disjunction concepts in Lukasiewicz fuzzy DLs. A binary disjunction can be represented adding a new binary variable y as {x1 + x2 ≤ z + y, y ≤ z, x1 + x2 ≥ z, y ∈ {0, 1}}. Again, n − 1 new binary variables would be needed but, similarly as before, considering the disjunction as an n-ary operator we would need only one new binary variable: n X xi ≤ z + (n − 1)y, i=1

y ≤ z, n X xi ≥ z, i=1 z ≤ x1, z ≤ x2, x1 ≤ z + y, x2 ≤ z + (1 − y),

y ∈ {0, 1}. 4

Optimizing Go¨edel N-ary Operators An n-ary conjunction can be represented using binary conjunctions adding restrictions of the form x1 ⊗G x2 = z, which can be encoded as follows:

The idea is that if y = 0, x1 = z is the minimum; whereas if y = 1, x2 = z is the minimum. This adds a new variable y, so in the case of n-ary conjunctions there would be n−1 new variables. Treating the conjunction as an n-ary operator, a more efficient representation is possible. An n-ary conjunction introduces a restriction of the form x1 ⊗G x2 ⊗ · · · ⊗ xn = z. To represent that the minimum of n variables xi is equal to z, we can use n binary variables yi such that if yi takes the value 0 then xi (representing the minimum) is equal to z, and such that the sum of the yi is 1, so z takes the value of some xi. Note that the minimum may not be unique. Such a representation is as follows:

z ≤ xi, for i ∈ {1, . . . , n}, xi ≤ z + yi, for i ∈ {1, . . . , n}, n X yi = 1, i=1 yi ∈ {0, 1}, for i ∈ {1, . . . , n}.

Now, we will show that it is possible to give a more efficient representation, Essentially, we need to encode n possible states. However, n possible states can be encoded using m = dlog2 ne new binary variables only. For instance, for n = 5, only dlog2 5e = 3 binary variables are necessary, where we use the encoding of the n = 5 states in Table 1 (b).

The main point is now to correctly encode the condition xi ≤ z + yi of the old encoding. We proceed as follows. Let bi be a string of length m, representing the value i − 1 in base 2 (1 ≤ i ≤ n). For instance, for i = 4, b = 011, as illustrated in the table above. Let us define the expression eij (1 ≤ i ≤ n, 1 ≤ j ≤ m) as: eij = yj if the jth bit of bi is 0 1 − yj otherwise.

For i = 4, we have b = 011 and, thus, e41 = 1 − y1, e42 = 1 − y2, and e43 = y3. Now we are ready to provide the whole encoding:

The first condition is the same as before. The second condition guarantees that xi ≤ z in the state bi. Finally, the third condition ensures that we are not addressing more than n states. For instance, for n = 5 we have: z ≤ xi, for i = 1, . . . , n m xi ≤ z + X eij, for i = 1, . . . , n

j=1 m X 2j−1yj ≤ n − 1, j=1 yj ∈ {0, 1}, for j = 1, . . . , m. z ≤ x1, z ≤ x2, z ≤ x3, z ≤ x4, z ≤ x5, x1 ≤ z + y1 + y2 + y3,

The case of the disjunction in G¨odel fuzzy DLs is dual. If an n-ary concept of the form (C1 t C2 t · · · t Cn) is represented using binary disjunctions, n − 1 new binary variables are needed. However, if we consider it as an n-ary concept, it is possible to use dlog2 ne new binary variables only:

z ≥ xi, for i = 1, . . . , n m xi + X eij ≥ z for i = 1, . . . , n

j=1 m X 2j−1yj ≤ n − 1, j=1

yj ∈ {0, 1} for j = 1, . . . , m. 5 Let us start with the case of trapezoidal functions, which introduce a restriction of the form trapezoidal(k1, k2, q1, q2, q3, q4)(xu) ≥ z. A restriction of that form can be represented by adding 5 new binary variables yi as follows: xu + (q1 − q2)xu + (k2 − q1)y2 ≤ k2, xu + (q1 − q2)xu + (k1 − q2)y2 ≥ k1 + q1 − q2, xu + (q4 − q3)xu + (k1 − q4)y4 ≥ k1, y1 + y2 + y3 + y4 + y5 = 1, yi ∈ {0, 1}, for i = 1, . . . , 5.

To reduce now the number of binary variables, the idea is to have 5 binary variables encoding the 5 possible states: xu ≤ q1 (y1 = 1), xu ∈ [q1, q2] (y2 = 1), xu ∈ [q2, q3] (y3 = 1), xu ∈ [q3, q4] (y4 = 1), and xu ≥ q4 (y5 = 1). However, as shown in Table 1 (b), it is possible to represent 5 states using only 3 variables.

The case of other fuzzy membership functions is similar. In triangular functions, a na¨ıve encoding introduces 4 new variables to represent the 4 possible states, but it is possible to consider only 2. Finally, in left and right shoulder functions, it is necessary to consider 3 states, which can be achieved by adding 2 new binary variables, instead of the 3 ones needed in the non-optimal encoding.

By considering the fact that even for moderate sized ontologies we may easily generate thousands of such constraints, it is evident that the number of saved binary variables n, and hence the number of saved assignments 2n, is non-negligible.

Acknowledgement This research work has been partially supported by the CICYT project TIN2013-46238-C4-4-R and DGA-FSE.

References

References

1. Arenas , M. , Botoeva , E. , Calvanese , D. , Ryzhikov , V. : Exchanging OWL2 QL knowledge bases . In: Proc. IJCAI . pp. 703 - 710 ( 2013 )

2. Arenas , M. , Botoeva , E. , Calvanese , D. , Ryzhikov , V. , Sherkhonov , E.: Exchanging description logic knowledge bases . In: Proc. KR . pp. 563 - 567 ( 2012 )

3. Arenas , M. , Pe´rez, J., Reutter , J.L. : Data exchange beyond complete data . J. ACM 60 ( 4 ), 28 : 1 - 28 : 59 ( 2013 )

4. Baader , F. : Least common subsumers and most specific concepts in a description logic with existential restrictions and terminological cycles . In: Proc. IJCAI . pp. 364 - 369 ( 2003 )

5. Baader , F. , Brandt , S. , Lutz , C. : Pushing the E L envelope . In: Proc. IJCAI . pp. 364 - 369 ( 2005 )

6. Cal`ı, A. , Gottlob , G. , Kifer , M. : Taming the infinite chase: Query answering under expressive relational constraints . J. Artif. Intell. Res . 48 , 115 - 174 ( 2013 )

7. Cali , A. , Gottlob , G. , Lukasiewicz , T. , Marnette , B. , Pieris , A. : Datalog+/ -: A family of logical knowledge representation and query languages for new applications . In: Proc. LICS . pp. 228 - 242 ( 2010 )

8. Cal`ı, A. , Gottlob , G. , Pieris , A. : Towards more expressive ontology languages: The query answering problem . Artif. Intell . 193 , 87 - 128 ( 2012 )

9. Calvanese , D. , De Giacomo , G. , Lembo , D. , Lenzerini , M. , Rosati , R. : Tractable reasoning and efficient query answering in description logics: TheDL-Lite family . J. Autom. Reasoning 39 ( 3 ), 385 - 429 ( 2007 )

10. Fagin , R. , Kimelfeld , B. , Kolaitis , P.G. : Probabilistic data exchange . J. ACM 58 ( 4 ), 15 : 1 - 15 : 55 ( 2011 )

11. Fagin , R. , Kolaitis , P.G. , Miller , R.J. , Popa , L. : Data exchange: Semantics and query answering . Theor. Comput. Sci . 336 ( 1 ), 89 - 124 ( 2005 )

12. Fuhr , N. , Ro¨lleke, T.: A probabilistic relational algebra for the integration of information retrieval and database systems . ACM Trans. Inf. Sys . 15 ( 1 ), 32 - 66 ( 1997 )

13. Green , T.J. , Karvounarakis , G. , Tannen , V. : Provenance semirings . In: Proc. PODS . pp. 31 - 40 ( 2007 )

14. Imielinski , T. , Witold Lipski , J.: Incomplete information in relational databases . J. ACM 31 ( 4 ), 761 - 791 ( 1984 )

15. Johnson , D.S.: A catalog of complexity classes . In: van Leeuwen, J . (ed.) Handbook of Theoretical Computer Science , vol. A, chap. 2 , pp. 67 - 161 . MIT Press ( 1990 )

16. Krisnadhi , A. , Lutz , C. : Data complexity in the E L family of description logics . In: Proc. LPAR , LNCS, vol. 4790 , pp. 333 - 347 . Springer ( 2007 )

17. Lenzerini , M. : Data integration: A theoretical perspective . In: Proc. PODS . pp. 233 - 246 ( 2002 )

18. Lukasiewicz , T. , Martinez , M.V. , Pieris , A. , Simari , G.I. : From classical to consistent query answering under existential rules . In: Proc. AAAI . pp. 1546 - 1552 ( 2015 )

19. Lukasiewicz , T. , Martinez , M.V. , Predoiu , L. , Simari , G.I. : Existential rules and Bayesian networks for probabilistic ontological data exchange . In: Proc. RuleML. LNCS , vol. 9202 , pp. 294 - 310 . Springer ( 2015 )

20. Papadimitriou , C.H.: Computational Complexity. Addison-Wesley ( 1994 )

21. Poggi , A. , Lembo , D. , Calvanese , D. , De Giacomo , G. , Lenzerini , M. , Rosati , R.: Linking data to ontologies . J. Data Sem . 10 , 133 - 173 ( 2008 )

22. Suciu , D. , Olteanu , D. , Re´, C. , Koch , C.: Probabilistic Databases. M & C ( 2011 )

23. Vardi , M.Y.: The complexity of relational query languages (extended abstract) . In: Proc. STOC . pp. 137 - 146 ( 1982 )

1. H. Al-Jamimi and M. Ahmed . Machine learning-based software quality prediction models: State of the art . In ICISA , pages 1 - 4 , 2013 .

2. T. L. Alves and J. Visser . Static estimation of test coverage . In SCAM , pages 55 - 64 . IEEE Computer Society, 2009 .

3. S. Auer , C. Bizer , G. Kobilarov, J. Lehmann , R. Cyganiak , and Z. Ives. DBpedia: A Nucleus for a Web of Open Data . In ISWC , volume 4825 , pages 722 - 735 . Springer, 2007 .

4. E. Bouwers , J. P. Correia , A. van Deursen , and J. Visser . Quantifying the analyzability of software architectures . In WICSA , pages 83 - 92 . IEEE, 2011 .

5. T. Do¨hmen, D. Ceolin , and J. Visser . Towards Building a Software Quality Prediction Model . Technical report , Software Improvement Group, 2015 .

6. F. Galton . Regression towards mediocrity in hereditary stature . The Journal of the Anthropological Institute of Great Britain and Ireland , 15 : 246 - 263 , 1886 .

7. X.-Y. Jing , S. Ying , Z.-W. Zhang , S.-S. Wu, and J. Liu . Dictionary learning based software defect prediction . In ICSE , pages 414 - 423 , 2014 .

8. S. Kan . Metrics and Models in Software Quality Engineering . Pearson, 2002 .

9. A. Kolmogorov . Sulla determinazione empirica di una legge di distribuzione . Giornale dell'Istituto Italiano degli Attuari , 4 : 1 - 11 , 1933 .

10. D. Milne and I. H. Witten . An open-source toolkit for mining wikipedia . Artif . Intell., 194 : 222 - 239 , 2013 .

11. A. T. Misirli and A. B. Bener . A mapping study on bayesian networks for software quality prediction . In RAISE , pages 7 - 11 , 2014 .

12. J. R. Norris . Markov chains. Cambridge University Press, 1998 .

13. R. Rosenthal and R. L. Rosnow . Contrast analysis : focused comparisons in the analysis of variance . Cambridge University press, 1985 .

14. N. Smirnov . Table for Estimating the Goodness of Fit of Empirical Distributions . The Annals of Mathematical Statistics , 19 ( 2 ): 279 - 281 , 1948 .

15. C. Spearman. The proof and measurement of association between two things . Amer. J. Psychol. , 15 : 72101 , 1904 .

16. F. Wilcoxon . Individual comparisons by ranking methods . Biometrics Bulletin , 1 : 80 - 83 , 1945 .

17. Wu , Z. and Palmer , M. Verb semantics and lexical selection . In ACL. ACL , 1994 .

1. C. Bobed , R. Yus , F. Bobillo , and E. Mena . Semantic reasoning on mobile devices: Do androids dream of efficient reasoners? Journal of Web Semantics , In press.

2. F. Bobillo and U. Straccia . fuzzyDL: An expressive fuzzy description logic reasoner . In Proceedings of the 17th IEEE International Conference on Fuzzy Systems (FUZZIEEE 2008 ), pages 923 - 930 , 2008 .

3. F. Bobillo and U. Straccia . On partitioning-based optimisations in expressive fuzzy description logics . In Proceedings of the 24th IEEE International Conference on Fuzzy Systems (FUZZ-IEEE 2015) , 2015 .

4. F. Bobillo and U. Straccia . Optimising fuzzy description logic reasoners with general concept inclusions absorption . Fuzzy Sets and Systems , In press.

5. V. Haarslev , H.-I. Pai , and N. Shiri . Optimizing tableau reasoning in ALC extended with uncertainty . In Proceedings of the 20th International Workshop on Description Logics (DL 2007 ), volume 250 , pages 307 - 314 . CEUR Workshop Proceedings, 2007 .

6. G. S. N. Simou , T. Mailis and G. Stamou . Optimization techniques for fuzzy description logics . In Proceedings of the 23rd International Workshop on Description Logics (DL 2010 ), volume 573 . CEUR Workshop Proceedings , 2010 .

7. H. M. Salkin and K. Mathur . Foundations of Integer Programming . North-Holland, 1989 .

8. U. Straccia . Foundations of Fuzzy Logic and Semantic Web Languages . CRC Studies in Informatics Series. Chapman & Hall , 2013 .