Archive for the ‘News’ Category

PARIS: Probabilistic Alignment of Relations, Instances, and Schema (website)

November 2nd, 2011
Comments Off

A website for PARIS

One of the main challenges that the Semantic Web faces is the integration of a growing number of independently designed ontologies. In this work, we present paris, an approach for the automatic alignment of ontologies. paris aligns not only instances, but also relations and classes. Alignments at the instance level cross-fertilize with alignments at the schema level. Thereby, our system provides a truly holistic solution to the problem of ontology alignment. The heart of the approach is probabilistic, i.e., we measure degrees of matchings based on probability estimates. This allows paris to run without any parameter tuning. We demonstrate the efficiency of the algorithm and its precision through extensive experiments. In particular, we obtain a precision of around 90 % in experiments with some of the world’s largest ontologies.

News , ,

Collège de France designated Serge Abiteboul to the Annual Chair in Information Technology and Digital Sciences for 2011-2012

October 4th, 2011
Comments Off

The inaugural lecture will take place at amphitheatre Halbwachs at Collège de France, Thursday March 8th 2012 at 18h.

The lectures will start next Wednesday from 10 to 11 AM followed by a seminar given by illustrious guests. You can find the calendar with more details about the guests and the date either :

News , , ,

The “Web Data Management and Distribution” book released

September 20th, 2011
Comments Off

The “Web Data Management and Distribution” book by Serge Abiteboul, Ioana Manolescu, Philippe Rigaux, Marie-Christine & Pierre Senellart (nicknamed Jorge) is officially launched on the Web:

It comes in full in PDF with slides and programming projects.

The book is available at Cambridge University Press

News , , ,

PhD defense of Alban Galland

September 19th, 2011
Comments Off

Alban Galland will defend his PhD, September 28th 2011 at 15:00, room 455 of PCRI at Gif-sur-Yvette (Plateau de Saclay)

Title: Distributed Data Management with Access Control
– Social Networks and Data of the Web

Abstract: The amount of information on the Web is spreading very rapidly. Users as
well as companies bring data to the network and are willing to share with
others. They quickly reach a situation where their information is hosted on
many machines they own and on a large number of autonomous systems
where they have accounts. Management of all this information is rapidly
becoming beyond human expertise. We introduce WebdamExchange, a
novel distributed knowledge-base model that includes logical statements
for specifying information, access control, secrets, distribution, and knowl-
edge about other peers. These statements can be communicated, replicated,
queried, and updated, while keeping track of time and provenance. The
resulting knowledge guides distributed data management. WebdamEx-
change model is based on WebdamLog, a new rule-based language for
distributed data management that combines in a formal setting deductive
rules as in Datalog with negation, (to specify intensional data) and active
rules as in Datalog¬¬ (for updates and communications). The model pro-
vides a novel setting with a strong emphasis on dynamicity and interactions
(in a Web 2.0 style). Because the model is powerful, it provides a clean
basis for the specification of complex distributed applications. Because it
is simple, it provides a formal framework for studying many facets of the
problem such as distribution, concurrency, and expressivity in the context
of distributed autonomous peers. We also discuss an implementation of a
proof-of-concept system that handles all the components of the knowledge
base and experiments with a lighter system designed for smartphones. We
believe that these contributions are a good foundation to overcome the
problems of Web data management, in particular with respect to access

News , , , ,

Marie-Christine Rousset on french web-radio about “Genèse d’un algorithme”

May 6th, 2011
Comments Off

Marie-Christine Rousset with Gilles Dowek and François Rechenmann participate in Xavier de La Porte podcast about Genèse d’un algorithme related to the paper on also in french.


Daniel and Yael joining Webdam

January 21st, 2011
Comments Off

Webdam is very happy to announce that Daniel Deutch and Yael Amsterdamer are joining the project beginning of February.

Daniel did his PhD with Tova Milo at Tel Aviv U., then a postdoc at the Computer & Information Science Department
in the University of Pennsylvania, Philadelphia.

Yael is starting a PhD also with Tova Milo.


Pierre defends his PhD

January 4th, 2011
Comments Off

Pierre Bourhis will defend his PhD, February 11th 2011, in room N107 of Parc-Club of Orsay.

Title: On the dynamics of active documents for distributed data management

Abstract: One of the major issues faced by Web applications is the management of evolving of data. In this thesis, we consider this problem and in particular the evolution of active documents. Active documents is a formalism describing the evolution of XML documents by activating Web services calls included in the document. It has already been used in the context of the management of distributed data axml.
The main contributions of this thesis are theoretical studies motivated by two systems for managing respectively stream applications and workflow applications. In a first contribution, we study the problem of view maintenance over active documents. The results served as the basis for an implementation of stream processors based on active documents called Axlog widgets. In a second one, we see active documents as the core of data centric workflows and consider various ways of expressing constraints on the evolution of documents. The implementation, called Axart, validated the approach of a data centric workflow system based on active documents.


Hyunjung Park visiting Webdam

December 1st, 2010
Comments Off

Hyunjung Park is visiting webdam Friday 17 December. He is a Ph.D. student in the Department of Electrical Engineering at Stanford University. His advisor is Jennifer Widom. He is the winner of the SIGMOD 2010 Programming Contest, organized by Pierre Senellart and Serge Abiteboul. Teams of contestants from degree-granting institutions had to develop an efficient distributed query engine on top of an in-memory index. The competition received much attention, with 29 teams from 23 different institutions over the world. H. Park will give a talk on its experience of the SIGMOD 2010 Programming Contest at 2pm in the meeting room G008 of INRIA-Saclay .

Title: SIGMOD 2010 Programming Contest

Abstract: Student teams have competed to build a distributed query engine in the SIGMOD 2010 Programming Contest. In this talk, H. Park will describe the task briefly and present the winning system. Specifically, he will cover the design choices and implementation issues for the query planner and executor. Also, he will discuss several optimizations and their effectiveness.


Moshe Vardi visiting Webdam

October 13th, 2010
Comments Off

Moshe Y. Vardi is visiting Webdam Wednesday 3 November. He is Karen Ostrum George Professor in Computational Engineering and Director of the Computer and Information Technology Institute ((Rice University, Houston, Texas). His interests focus on applications of logic to computer science, including database theory, finite-model theory, knowledge in multi-agent systems, computer-aided verification and reasoning, and teaching logic across the curriculum. He will present his work on propositional satisfiability in the meeting room of ENS Cachan (Pavillon des Jardins) at 11:00am.

Title: Symbolic Techniques in Propositional Satisfiability Solving

Abstract: Search-based techniques in propositional satisfiability (SAT) solving have been enormously successful, leading to what is becoming known as the “SAT Revolution”. Essentially all state-of-the-art SAT solvers are based on the Davis-Putnam-Logemann-Loveland (DPLL) technique, augmented with backjumping and conflict learning. Much of current research in this area involves refinements and extensions of the DPLL technique. Yet, due to the impressive success of DPLL, little effort has gone into investigating alternative techniques. This work focuses on symbolic techniques for SAT solving, with the aim of stimulating a broader research agenda in this area.

Refutation proofs can be viewed as a special case of constraint propagation, which is a fundamental technique in solving constraint-satisfaction problems. The generalization lifts, in a uniform way, the concept of refutation from Boolean satisfiability problems to general constraint-satisfaction problems. On the one hand, this enables us to study and characterize basic concepts, such as refutation width, using tools from finite-model theory. On the other hand, this enables us to introduce new proof systems, based on representation classes, that have not been considered up to this point. We consider ordered binary decision diagrams (OBDDs) as a case study of a representation class for refutations, and compare their strength to well-known proof systems, such as resolution, the Gaussian calculus, cutting planes, and Frege systems of bounded alternation-depth. In particular, we show that refutations by ODBBs polynomially simulate resolution and can be exponentially stronger.

We then describe an effort to turn OBDD refutations into OBBD decision procedures. The idea of this approach, which we call “symbolic quantifier elimination”, is to view an instance of propositional satisfiability as an existentially quantified propositional formula. Satisfiability solving then amounts to quantifier elimination; once all quantifiers have been eliminated we are left with either 1 or 0. Our goal here is to study the effectiveness of symbolic quantifier elimination as an approach to satisfiability solving. To that end, we conduct a direct comparison with the DPLL-based ZChaff, as well as evaluate a variety of optimization techniques for the symbolic approach. In comparing the symbolic approach to ZChaff, we evaluate scalability across a variety of classes of formulas. We find that no approach dominates across all classes. While ZChaff dominates for many classes of formulas, the symbolic approach is superior for other classes of formulas.

Finally, we turn our attention to Quantified Boolean Formulas (QBF) solving. Much recent work has gone into adapting techniques that were originally developed for SAT solving to QBF solving. In particular, QBF solvers are often based on SAT solvers. Most competitive QBF solvers are search-based. Here we describe an alternative approach to QBF solving, based on symbolic quantifier elimination. We extend some symbolic approaches for SAT solving to symbolic QBF solving, using various decision-diagram formalisms such as OBDDs and ZDDs. In both approaches, QBF formulas are solved by eliminating all their quantifiers. Our first solver, QMRES, maintains a set of clauses represented by a ZDD and eliminates quantifiers via multi-resolution. Our second solver, QBDD, maintains a set of OBDDs, and eliminate quantifiers by applying them to the underlying OBDDs. We compare our symbolic solvers to several competitive search-based solvers. We show that QBDD is not competitive, but QMRESS compares favorably with search-based solvers on various benchmarks consisting of non-random formulas.


Proceedings Dagstuhl 2010

August 20th, 2010
Comments Off

The proceedings of the

Dagstuhl Seminar 10151 “Enabling Holistic Approaches to Business Process Lifecycle Management”
S. Abiteboul, A. Koschmider, A. Oberweis, J. Su (Eds.)

have been published.  They can be accessed through

News ,