Many application areas (e.g., concerning the semantic web or biological applications) consider graph structured data, where the data consists of a finite set of nodes connected by labeled edges. For querying such data one usually needs to specify types of paths along which nodes are connected. A widely studied class of queries for graph structured databases are the conjunctive regular path queries, where types of paths can be described by regular expressions specifying labels along the paths. For modern applications, however, also more expressive query languages are desirable, allowing not only to specify regular properties of path labels, but also to compare paths based on, e.g., their lengths, labels, or similarity. The aim of this talk is to give an overview of recent developments in this area. Special emphasis will be put on query languages, their expressive power, and their complexity concerning query evaluation and static analysis. With kind support of the Wolfgang Pauli Institut (WPI).

• Thematic program: Databases and Ontologies in Advanced Information Systems (2010, Prolongation from 2009)
• Thematic program: Logic based reasoning and data mining on the web (2012)

Description Logics (DLs) play a central role as formalisms for representing ontologies and reasoning about them. They are the logical underpinning of the OWL languages for the Semantic Web, and are increasingly employed in many application areas. This lecture will introduce the basics of DLs. We will discuss the knowledge modeling capabilities of some of the most prominent DLs and present some classic DL reasoning services, like classification, consistency, and instance checking. In the second part of the lecture we will approach the use of DL ontologies for data access, and introduce the increasingly popular framework in which data repositories are queried through DL ontologies. We will discuss the main challenges that arise in this setting and describe some query answering techniques. The computational complexity of the latter will also be briefly discussed.

• Thematic program: Logic based reasoning and data mining on the web (2012)
• Event: "Reasoning Web 2012" Summer School (2012)

Description Logics (DLs) play a central role as formalisms for representing ontologies and reasoning about them. They are the logical underpinning of the OWL languages for the Semantic Web, and are increasingly employed in many application areas. This lecture will introduce the basics of DLs. We will discuss the knowledge modeling capabilities of some of the most prominent DLs and present some classic DL reasoning services, like classification, consistency, and instance checking. In the second part of the lecture we will approach the use of DL ontologies for data access, and introduce the increasingly popular framework in which data repositories are queried through DL ontologies. We will discuss the main challenges that arise in this setting and describe some query answering techniques. The computational complexity of the latter will also be briefly discussed.

• Thematic program: Logic based reasoning and data mining on the web (2012)
• Event: "Reasoning Web 2012" Summer School (2012)

In this lecture we introduce Datalog, a powerful language for expressing complex queries over relational data and a means for declarative problem solving. To argue that Datalog is particularly appealing for the Semantic Web, we will identify some of the expressivity limitations of the traditional SQL-like query languages, and show how they can be overcome using Datalog. We will further discuss extensions of Datalog that allow to capture some of the ontology languages of the OWL family, and can thus be used to reason about ontologies.

• Thematic program: Logic based reasoning and data mining on the web (2012)
• Event: "Reasoning Web 2012" Summer School (2012)

In this lecture we introduce Datalog, a powerful language for expressing complex queries over relational data and a means for declarative problem solving. To argue that Datalog is particularly appealing for the Semantic Web, we will identify some of the expressivity limitations of the traditional SQL-like query languages, and show how they can be overcome using Datalog. We will further discuss extensions of Datalog that allow to capture some of the ontology languages of the OWL family, and can thus be used to reason about ontologies.

• Thematic program: Logic based reasoning and data mining on the web (2012)
• Event: "Reasoning Web 2012" Summer School (2012)

Since about a decade Semantic Wikis have been proposed, systems have been conceived, developed and used for various purposes. This article aims first at a comprehensive state-of-the-art on the research on Semantic Wiki stressing the concepts and techniques making Semantic Wikis easy to use by a wide, and possibly unskilled, audience. The further describes applications, or application use cases, that have driven the research on Semantic Wikis. Finally, the article addresses software techniques and architectures that have been proposed for Semantic Wikis.

• Thematic program: Logic based reasoning and data mining on the web (2012)
• Event: "Reasoning Web 2012" Summer School (2012)

Since about a decade Semantic Wikis have been proposed, systems have been conceived, developed and used for various purposes. This article aims first at a comprehensive state-of-the-art on the research on Semantic Wiki stressing the concepts and techniques making Semantic Wikis easy to use by a wide, and possibly unskilled, audience. The further describes applications, or application use cases, that have driven the research on Semantic Wikis. Finally, the article addresses software techniques and architectures that have been proposed for Semantic Wikis.

• Thematic program: Logic based reasoning and data mining on the web (2012)
• Event: "Reasoning Web 2012" Summer School (2012)

Since about a decade Semantic Wikis have been proposed, systems have been conceived, developed and used for various purposes. This article aims first at a comprehensive state-of-the-art on the research on Semantic Wiki stressing the concepts and techniques making Semantic Wikis easy to use by a wide, and possibly unskilled, audience. The further describes applications, or application use cases, that have driven the research on Semantic Wikis. Finally, the article addresses software techniques and architectures that have been proposed for Semantic Wikis.

• Thematic program: Logic based reasoning and data mining on the web (2012)
• Event: "Reasoning Web 2012" Summer School (2012)

SPARQL is now widely used as the standard query language for RDF. Since the release of its first version in 2008, the W3C group in charge of the standard has been working on extensions of the language to be included in the new version, SPARQL 1.1. These extensions include several interesting and very useful features for querying RDF.

In this tutorial, we survey two key features of SPARQL 1.1: Federation and navigation capabilities. We focus on the formalization of these two features, in particular, of their syntax and semantics. We analyze some classical theoretical problems such as expressiveness and complexity, and discuss some algorithmic properties. Moreover, we present some important recently discovered issues regarding the normative semantics of federation and navigation in SPARQL 1.1, specifically, on the impossibility of answering some unbounded federated queries and the high computational complexity of the evaluation problem for queries including navigation functionalities. We argue that these issues may have a significant impact on the adoption of the new standard, and we discuss on possible alternatives and their implications.

• Thematic program: Logic based reasoning and data mining on the web (2012)
• Event: "Reasoning Web 2012" Summer School (2012)

SPARQL is now widely used as the standard query language for RDF. Since the release of its first version in 2008, the W3C group in charge of the standard has been working on extensions of the language to be included in the new version, SPARQL 1.1. These extensions include several interesting and very useful features for querying RDF.

In this tutorial, we survey two key features of SPARQL 1.1: Federation and navigation capabilities. We focus on the formalization of these two features, in particular, of their syntax and semantics. We analyze some classical theoretical problems such as expressiveness and complexity, and discuss some algorithmic properties. Moreover, we present some important recently discovered issues regarding the normative semantics of federation and navigation in SPARQL 1.1, specifically, on the impossibility of answering some unbounded federated queries and the high computational complexity of the evaluation problem for queries including navigation functionalities. We argue that these issues may have a significant impact on the adoption of the new standard, and we discuss on possible alternatives and their implications.

• Thematic program: Logic based reasoning and data mining on the web (2012)
• Event: "Reasoning Web 2012" Summer School (2012)

Ontologies play an important role for the success of the Semantic Web. Due to the dynamic nature of the Web, one can hardly expect to rely on ontologies with precise definitions and without any error. Thus, reasoning with uncertainty and dealing with inconsistency are two important issues in ontology engineering. In this tutorial, we will first introduce probabilistic description logics and possibilistic description logics, two important formalisms to represent and reasoning with uncertain and inconsistent ontologies. We discuss the relationship and difference betwen these two formalisms. We will then consider the dynamics of ontologies and focus on the problem of revising one ontology with another ontology. This problem is closely related to the problem of belief revision, which has been widely discussed in the literature. We give an overview of approaches to revising ontologies when inconsistencies occur.

• Thematic program: Logic based reasoning and data mining on the web (2012)
• Event: "Reasoning Web 2012" Summer School (2012)

Ontologies play an important role for the success of the Semantic Web. Due to the dynamic nature of the Web, one can hardly expect to rely on ontologies with precise definitions and without any error. Thus, reasoning with uncertainty and dealing with inconsistency are two important issues in ontology engineering. In this tutorial, we will first introduce probabilistic description logics and possibilistic description logics, two important formalisms to represent and reasoning with uncertain and inconsistent ontologies. We discuss the relationship and difference betwen these two formalisms. We will then consider the dynamics of ontologies and focus on the problem of revising one ontology with another ontology. This problem is closely related to the problem of belief revision, which has been widely discussed in the literature. We give an overview of approaches to revising ontologies when inconsistencies occur.

• Thematic program: Logic based reasoning and data mining on the web (2012)
• Event: "Reasoning Web 2012" Summer School (2012)

The RDF data which arrives in multiple, continuous, rapid and time-varying data streams has become more popular in real-time data sources like sensor data, social network. This time-dependent linked data, called Linked Stream Data, motivated several work in proposing data models associated with processing engines. This paper gives an overview about Linked Data Stream and the state of the art of processing models and techniques. In addition, by giving a survey on relevant work and technologies, the paper explores new issues and challenges in new requirements, query languages and query processing.

• Thematic program: Logic based reasoning and data mining on the web (2012)
• Event: "Reasoning Web 2012" Summer School (2012)

The RDF data which arrives in multiple, continuous, rapid and time-varying data streams has become more popular in real-time data sources like sensor data, social network. This time-dependent linked data, called Linked Stream Data, motivated several work in proposing data models associated with processing engines. This paper gives an overview about Linked Data Stream and the state of the art of processing models and techniques. In addition, by giving a survey on relevant work and technologies, the paper explores new issues and challenges in new requirements, query languages and query processing.

• Thematic program: Logic based reasoning and data mining on the web (2012)
• Event: "Reasoning Web 2012" Summer School (2012)

The recent availability of geospatial information as linked open data has generated new interest in geospatial query processing and reasoning, a topic with a long tradition of research in the areas of databases and artificial intelligence. In this paper we survey recent advances in this important research topic concentrating on issues of data modeling and querying.

• Thematic program: Logic based reasoning and data mining on the web (2012)
• Event: "Reasoning Web 2012" Summer School (2012)

The recent availability of geospatial information as linked open data has generated new interest in geospatial query processing and reasoning, a topic with a long tradition of research in the areas of databases and artificial intelligence. In this paper we survey recent advances in this important research topic concentrating on issues of data modeling and querying.

• Thematic program: Logic based reasoning and data mining on the web (2012)
• Event: "Reasoning Web 2012" Summer School (2012)

The web has become a pig sty—everyone dumps information at random places and in random shapes. Try to find the cheapest apartment in Oxford considering rent, travel, tax and heating costs; or a cheap, reasonable reviewed 11" laptop with an SSD drive.

Data extraction flushes structured information out of this sty: It turns mostly unstructured web pages into highly structured knowledge. In this chapter, we give a gentle introduction to data extraction including pointers to existing systems. We start with an overview and classification of data extraction systems along two primary dimensions, the level of supervision and the considered scale. The rest of the chapter is the organized along the first of these dimensions: In the first part, we discuss supervised data extraction, where a human user identifies for each site examples of the relevant data and the system generalizes these examples into extraction programs. We focus particularly on declarative and rule-based paradigms. In the second part, we turn to fully automated (or unsupervised) approaches where the system by itself identifies the relevant data and fully automatically extracts data from many websites. Ontologies or schemata have proven invaluable to guide unsupervised data extraction and we will present an overview of the existing approaches and the different way in which they are using Ontologies.

• Thematic program: Logic based reasoning and data mining on the web (2012)
• Event: "Reasoning Web 2012" Summer School (2012)

The web has become a pig sty—everyone dumps information at random places and in random shapes. Try to find the cheapest apartment in Oxford considering rent, travel, tax and heating costs; or a cheap, reasonable reviewed 11" laptop with an SSD drive.

Data extraction flushes structured information out of this sty: It turns mostly unstructured web pages into highly structured knowledge. In this chapter, we give a gentle introduction to data extraction including pointers to existing systems. We start with an overview and classification of data extraction systems along two primary dimensions, the level of supervision and the considered scale. The rest of the chapter is the organized along the first of these dimensions: In the first part, we discuss supervised data extraction, where a human user identifies for each site examples of the relevant data and the system generalizes these examples into extraction programs. We focus particularly on declarative and rule-based paradigms. In the second part, we turn to fully automated (or unsupervised) approaches where the system by itself identifies the relevant data and fully automatically extracts data from many websites. Ontologies or schemata have proven invaluable to guide unsupervised data extraction and we will present an overview of the existing approaches and the different way in which they are using Ontologies.

• Thematic program: Logic based reasoning and data mining on the web (2012)
• Event: "Reasoning Web 2012" Summer School (2012)

This chapter gives an extended introduction to the lightweight profiles OWL EL, OWL QL, and OWL RL of the Web Ontology Language OWL. Those three ontology language standards are sublanguages of OWL DL that are restricted in ways that significantly simplify ontological reasoning. Compared to OWL DL as a whole, reasoning algorithms for the OWL profiles show higher performance, are easier to implement, and can scale to larger amounts of data. Since ontological reasoning is of great importance for designing and deploying OWL ontologies, the profiles are highly attractive for many applications. These advantages come at a price: various modelling features of OWL are not available in all or some of the OWL profiles. Moreover, the profiles are mutually incomparable in the sense that each of them offers a combination of features that is available in none of the others. This chapter provides an overview of these differences and explains why some of them are essential to retain the desired properties. To this end, we recall the relationship between OWL and description logics (DLs), and show how each of the profiles is typically treated in reasoning algorithms.

• Thematic program: Logic based reasoning and data mining on the web (2012)
• Event: "Reasoning Web 2012" Summer School (2012)

This chapter gives an extended introduction to the lightweight profiles OWL EL, OWL QL, and OWL RL of the Web Ontology Language OWL. Those three ontology language standards are sublanguages of OWL DL that are restricted in ways that significantly simplify ontological reasoning. Compared to OWL DL as a whole, reasoning algorithms for the OWL profiles show higher performance, are easier to implement, and can scale to larger amounts of data. Since ontological reasoning is of great importance for designing and deploying OWL ontologies, the profiles are highly attractive for many applications. These advantages come at a price: various modelling features of OWL are not available in all or some of the OWL profiles. Moreover, the profiles are mutually incomparable in the sense that each of them offers a combination of features that is available in none of the others. This chapter provides an overview of these differences and explains why some of them are essential to retain the desired properties. To this end, we recall the relationship between OWL and description logics (DLs), and show how each of the profiles is typically treated in reasoning algorithms.

• Thematic program: Logic based reasoning and data mining on the web (2012)
• Event: "Reasoning Web 2012" Summer School (2012)

I will provide an overview of computational argumentation, focusing on abstract argumentation and assumption-based argumentation, as well as uses of these forms of argumentation in Web contexts, and in particular Semantic Web as well as Social Networks contexts. I will outline achievements to date as well as open issues and challenges.

• Thematic program: Logic based reasoning and data mining on the web (2012)
• Event: "Reasoning Web 2012" Summer School (2012)

I will provide an overview of computational argumentation, focusing on abstract argumentation and assumption-based argumentation, as well as uses of these forms of argumentation in Web contexts, and in particular Semantic Web as well as Social Networks contexts. I will outline achievements to date as well as open issues and challenges.

• Thematic program: Logic based reasoning and data mining on the web (2012)
• Event: "Reasoning Web 2012" Summer School (2012)

Recently, an answer-set programming (ASP) formalism of logic programing with the answer-set semantics has been extended to the full first-order setting. Earlier an extension of first-order logic with inductive definitions, the logic FO(ID), was proposed as a knowledge representation formalism and developed as an alternative ASP language. We present characterizations of these formalisms in terms of concepts of infinitary propositional logic. We use them to find a direct connection between the first-order ASP and the logic FO(ID) under some restrictions on the form of theories (programs) considered.

• Thematic program: Logic based reasoning and data mining on the web (2012)

Dung's argumentation framework is by far the most widely adopted formal model for abstract argumentation studies. While it has proved a powerful tool for theoretical analysis, questions may arise about its expressiveness and actual usefulness in practical contexts. After briefly recalling the basic concepts about Dung's framework, the talk will discuss merits and limits of this formalism and draw some perspectives about current and future research directions.

• Thematic program: Logic based reasoning and data mining on the web (2012)

With this seminar we would like to introduce you to the conceptual framework and the research results we obtained in Messina on analysing some of the user-generated content now available from Online Social Networks (OSNs). We will describe how, starting from research in Web data extraction, we have become interested in different issues that are now becoming of great interest, in view of the glory (so to speak) and almost-ubiquity of OSNs and of their ever-increasing base of content-generating users. We will begin with the extraction and analysis of [snapshots of] the Facebook friendship graph: what can (still) be done? How to study FB friendship and its evolution? We will describe the main features of two (large samples) we extracted from Facebook by applying two different sampling strategies. Extracted samples have been studied by applying methods which are largely accepted in the field of Complex Network Analysis (vertex degree distribution, clustering coeffcient, diameters and so on). Second, we will cover the topic of community detection inside OSN, a problem of obvious relevance and notorious computational complexity. We briefly glance at our solution, the CONCLUDE algorithm, and argue for its effectiveness and accuracy. Our results are twofold: on one hand we designed randomized algorithms to weight network edges and this tasks proves to be useful to improve the accuracy of the whole community detection problem. On the other hand I will illustrate some experimentas showing that our approach outperforms other, well-known algorithms when applied on large, real-world OSN instances. Finally, we will introduce our latest work on the aNobii network of book-lovers (bibliophiles); we studied the intensity of a user's participation to the SN in terms of i) joining groups (e.g., that on French literature) or assigning tags to books they've read. We have designed, implemented and validated a sampling algorithm that finds a good approximation of the probability distribution of joint user profiles. Our algorithm can be seen as an instantiation of the AA meta-algorithm of Dagum, Karp et al. Its complexity is controlled by the number of samples of a certain class it must find, even though the number of iterations is not fixed a priori; the overall error is bounded. These results where obtained in a joint research effort with P. De Meo, E. Ferrara, G. Fiumara and S. Catanese.

• Thematic program: Logic based reasoning and data mining on the web (2012)