Query Optimization for the Semantic Web
Semantic Web, Ontologies and Databases

A workshop at Universidad Simón Bolívar supported by the Spanish Agencia Española de Cooperación Internacional (AECI) under the project "Mecanismos de Optimización y Evaluación para consultar eficientemente la Web Semántica en la Administración Pública Electrónica".

Feb 11-12, 2008, Universidad Simón Bolívar, CBI Sala Multimedia de Post-Grado and CBI 140.

Speakers Abstracts Program&Materials Venue

Speakers

Abstracts

Tutorial (Feb 11- 8:30am-12:30pm) CBI Sala Multimedia de Post-Grado, 3er Piso

Answer Set Programming for the Semantic Web

Axel Polleres, DERI, National University of Ireland, Galway

The purpose of this tutorial is to get the audience familiar with the Answer Set Programming (ASP) Paradigm in the perspective of
its fruitful usage for Semantic Web applications. ASP is a declarative programming paradigm with its roots in Knowledge
Representation and Logic Programming.

Systems and languages based on ASP are ready for tackling many of the challenges the Semantic Web offers, and in particular, are good
candidates for solving a variety of issues which have been delegated to the Rule/Logic Layers in the Semantic Web vision. ASP systems
are scalable, allow to mix monotonic with nonmonotonic reasoning, permit to combine rules with ontologies, and can interface external
reasoners. Moreover, ASP is especially tailored at solving configuration and matchmaking problems involving reasoning with
preferences by featuring easy to use, fully declarative soft & hard constraint specification languages.

We introduce the attendees to the ASP basics and its principal extensions tailored at Semantic Web applications. We discuss the
current impact of Answer Set Programming in the Semantic Web Area and possible future directions. Applications and exercises are
presented.

Talks (Feb 12- 2:00pm-6:00pm) CBI 140, 1er Piso

Semantic Web, Ontologies and Databases- An Overview

María Esther Vidal, Universidad Simón Bolívar, Venezuela

Emerging technologies such as the Semantic Web, Semantic Grid a Emerging technologies such as the Semantic Web, Semantic Grid and P2P have made available a huge number of very large data sources in almost any knowledge domain. This widespread explosion of Web accessible resources has lead to new challenges on the traditional problems of data integration, query evaluation and data ranking based on some criteria. For example, efficient techniques have to be defined to rewrite or evaluate queries against a large number of huge data sources; also strategies to approximate the best objects based on ranking criteria are required. In this talk, we will provide an overview of the projects developed by the database group of the University Simón Bolívar to achieve some of these challenges. We will focus on the technique presented in [Arvelo & Bonet & Vidal AAAI 2006], that encodes query-rewriting problems as propositional theories. Thus, using modern SAT solvers, this solution is able to produce maximal-contained rewritings, while the execution time is at least a couple of orders of magnitude smaller than the time required by the state-of-the-art solutions.

A Directed Hypergraph Model for RDF

Amadís Antonio Martínez Morales, Universidad de Carabobo, Venezuela, and
María Esther Vidal, Universidad Simón Bolívar, Venezuela

RDF is a proposal of the W3C to express metadata about resources in the Web. The RDF data model allows several representations, each one with its own limitations at expressive power and support for the tasks of query answering and semantic reasoning. In this paper, we present a directed hypergraph model for RDF to represent RDF documents efficiently. We compare our approach with other proposals and we study its impact on the tasks of query answering and semantic inference. Finally, we explain the objectives that we plan to achieve in the context of this work.

Cost-based techniques to Compose Web Services

Eduardo Blanco and María-Esther Vidal, Universidad Simón Bolívar, Venezuela

In this talk, we present three cost-based algorithms to identify orderings of Web Services compositions. These algorithms use
 techniques to prune the space of possibilities while minimizing evaluating costs.  The first algorithm, DP-SAM, extends the greedy
algorithm SAM and traverses the space by using a dynamic-based programming technique; a cost-based criteria is used to select the solutions that survive at each iteration. The second algorithm, BF-SAM, combines a best first strategy with a dynamic-programing technique and produces good Web Service compositions by traversing a small portion of the search space. Finally, the PN-SAM uses the unfolding technique of Pettri Nets to identify optimal Web Service compositions. To evaluate the behavior of these algorithms, we compare them to SAM and to an exhaustive dynamic programing technique through quality of plans.  We present an empirical study of the quality of the solutions identified by the proposed techniques. We show that the quality of our solutions are similar to those produce by the exhaustive approach and also outperform the ones identified by SAM, while optimization time is in the same order of magnitude than that of SAM.


Representing ReActive Knowledge in Ontologies

Elsa Tovar, Universidad de Carabobo, Venezuela
and María-Esther Vidal, Universidad Simón Bolívar, Venezuela

Proceedings Template - WORD

Reactive data behavior expresses changes over data when events occur and data satisfy specific conditions. The most widely used approach to process reactive behavior is the ECA rules paradigm and has been extensively study by the database and language communities. In the context of the Semantic Web, reactive knowledge is encoded in ontologies by using ECA rules, and
the events that fire these rules, are considered as transactional data, which are independent of the classes and properties represented in the ontology. Active knowledge cannot be used to derive new properties of the data instances, and new reactive behavior information cannot be inferred directly from the schema; therefore, the power of the inference process is limited to what can be inferred from the classes, properties and instances. In this paper, we describe an alternative approach to aim the enrichment of the Semantic Web with dynamism. In this talk, we propose an active ontology formalism to express reactive behavior. In our proposed
formalism, events are categorized as first-class concepts of the ontology, and in conjunction with classes, properties and instances, are considered during the query answering and reasoning tasks. 

Approximate Techniques to Rank Database Objects based on Authority Flow

Luis Ibáñez and Héctor Rodríguez and María-Esther Vidal, Universidad Simón Bolívar, Venezuela

<big></big>

Emerging technologies have make available a large number of data, which may be related to relevant and important objects. Popular authority-flow based ranking techniques have shown to be precise to discriminate hyperlinked objects in terms of relevance and importance; particularly, these ranking techniques are able to distinguish relevant and important objects or Golden objetcs. However, evaluating authority-flow based techniques is usually expensive in large datasets. In this talk, we present the problem of identifying Golden objects efficiently and we propose two approximated solutions to this problem. First, we propose a solution defined in terms of the Direct Sampling technique proposed to sample Bayesian networks. Second, we adapt paths sampling techniques to identy path that conduct to Golden objects. We conduct an experimental study on large biological datasets. Our experimental results show that the proposed techniques are able to identify the 90% of Golden objects, while time needed is less than 50% of the execution time of the exact solution.

Program & Material

Feb 11:
Feb 12:

Venue Information

Universidad Simón Bolívar , room CBI 140.

Valle de Sartenejas, Baruta
Caracas 1080, Venezuela


Map of Universidad Rey Juan Carlos, DII/070 Tulipán s/n 28933 Móstoles Madrid, España


Organized by

Universidad Simón Bolívar   Universidad Rey Juan Carlos     deri institute     

Contact person: Axel Polleres
                           Edna Ruckhaus,
                           María-Esther Vidal

Valid XHTML 1.0 Strict