Serge Abiteboul

CSL Conference 2012 Conference Paper

Sharing Distributed Knowledge on the Web (Invited Talk)

• Serge Abiteboul

To share information, we propose to see the Web as a knowledge base consisting of distributed logical facts and rules. Our objective is to help Web users finding information, as well as controlling their own, using automated reasoning over this knowledge base towards improving the quality of service and of data. For this, we introduce Webdamlog, a Datalog-style language with rule delegation. We mention the implementation of a system to support this language as well as standard communications and security protocols.

TIME Conference 2009 Invited Paper

The AXML Artifact Model

• Serge Abiteboul
• Pierre Bourhis
• Alban Galland
• Bogdan Marinoiu

Towards a data-centric workflow approach, we introduce an artifact model to capture data and workflow management activities in distributed settings. The model is built on Active XML, i. e. , XML trees including Web service calls. We argue that the model captures the essential features of business artifacts as described informally in [A. Nigam and N. Caswell (2003)] or discussed in [R. Hull (2008)]. To illustrate, we briefly consider the monitoring of distributed systems and the verification of temporal properties for them.

TCS Journal 2002 Journal Article

Correspondence and translation for heterogeneous data

• Serge Abiteboul
• Sophie Cluet
• Tova Milo

Data integration often requires a clean abstraction of the different formats in which data are stored, and means for specifying the correspondences/relationships between data in different worlds and for translating data from one world to another. For that, we introduce in this paper a middleware data model that serves as a basis for the integration task, and a declarative rules language for specifying the integration. We show that using the language, correspondences between data elements can be computed in polynomial time in many cases, and may require exponential time only when insensitivity to order or duplicates are considered. Furthermore, we show that in most practical cases the correspondence rules can be automatically turned into translation rules to map data from one representation to another. Thus, a complete integration task (derivation of correspondences, transformation of data from one world to the other, incremental integration of a new bulk of data, etc.) can be specified using a single set of declarative rules.

SODA Conference 2001 Conference Paper

Compact labeling schemes for ancestor queries

• Serge Abiteboul
• Haim Kaplan
• Tova Milo

TCS Journal 2000 Journal Article

Queries and computation on the web

• Serge Abiteboul
• Victor Vianu

The paper introduces a model of the Web as an infinite, semistructured set of objects. We reconsider the classical notions of genericity and computability of queries in this new context and relate them to styles of computation prevalent on the Web, based on browsing and searching. We revisit several well-known declarative query languages (first-order logic, Datalog, and Datalog with negation) and consider their computational characteristics in terms of the notions introduced in this paper. In particular, we are interested in languages or fragments thereof which can be implemented by browsing, or by browsing and searching combined. Surprisingly, stratified and well-founded semantics for negation turn out to have basic shortcomings in this context, while inflationary semantics emerges as an appealing alternative.

I&C Journal 1998 Journal Article

Reflective Relational Machines

• Serge Abiteboul
• Christos H Papadimitriou
• V Vianu

We propose a model of database programming withreflection(dynamic generation of queries within the host programming language), called thereflective relational machine, and characterize the power of this machine in terms of known complexity classes. In particular, the polynomial time restriction of the reflective relational machine is shown to express PSPACE, and to correspond precisely to uniform circuits of polynomial depth and exponential size. This provides an alternative, logic based formulation of the uniform circuit model, which may be more convenient for problems naturally formulated in logic terms, and establishes that reflection allows for more “intense” parallelism, which is not attainable otherwise (unless P=PSPACE). We also explore the power of the reflective relational machine subject to restrictions on the number of variables used, emphasizing the case of sublinear bounds.

TCS Journal 1996 Journal Article

Foreword

• Serge Abiteboul
• Eli Shamir

TCS Journal 1995 Journal Article

Computing with infinitary logic

• Serge Abiteboul
• Moshe Y. Vardi
• Victor Vianu

Most recursive extensions of the first-order queries converge around two central classes of queries: fixpoint and while. Infinitary logic (with finitely many variables) is a very powerful extension of these languages which provides an elegant unifying formalism for a wide variety of query languages. However, neither the syntax nor the semantics of infinitary logic are effective, and its connection to practical query languages has been largely unexplored. We relate infinitary logic to another powerful extension of fixpoint and while, called relational machine, which highlights the computational style of these languages. Relational machines capture the kind of computation occurring when a query language is embedded in a host programming language, as in C+SQL. The main result of this paper is that relational machines correspond to the natural effective fragment of infinitary logic. Other well-known query languages are related to infinitary logic using syntactic restrictions formulated in language-theoretic terms. For example, it is shown that while corresponds to infinitary logic formulas which can be described by a regular language. As a side effect to these results, we obtain interesting normal forms for effective infinitary logic formulas.

TCS Journal 1993 Journal Article

Foreword

• Serge Abiteboul
• Paris Kanellakis

TCS Journal 1991 Journal Article

Fundamental properties of deterministic and nondeterministic extensions of Datalog

• Serge Abiteboul
• Eric Simon

Fundamental properties of deterministic and nondeterministic extensions of Datalog from Abiteboul and Vianu (1988) are studied. The extensions involve the use of negative literals both in bodies and heads of rules. Negative literals in heads are interpreted as deletions. A deterministic semantics is obtained by firing in parallel all applicable rules. The nondeterministic semantics results from firing (nondeterministically) one rule at a time. In the nondeterministic case, programs do not describe functions but relations between database states. In both cases, the result is an increase in expressive power over Datalog. The price for it is that programs do not always terminate. We study when a program (i) is such that on a given input, all its successful computations reach a unique fixpoint, (ii) yields at least one output on every input and (iii) has only loop-free computations. We also show how to simulate programs containing loops by loop-free programs.

STOC Conference 1991 Conference Paper

Generic Computation and Its Complexity

• Serge Abiteboul
• Victor Vianu

TCS Journal 1991 Journal Article

On the representation and querying of sets of possible worlds

• Serge Abiteboul
• Paris Kanellakis
• Gösta Grahne

We represent a set of possible worlds using an incomplete information database. The representation techniques that we study range from the very simple Codd-table (a relation over constants and uniquely occurring variables called nulls) to much more complex mechanisms involving views of conditioned-tables (programs applied to Codd-tables augmented by equality and inequality conditions). (1) We provide matching upper and lower bounds on the data-complexity of testing containment, membership and uniqueness for sets of possible worlds. We fully classify these problems with respect to our representations. (2) We investigate the data-complexity of querying incomplete information databases for both possible and certain facts. For each fixed positive existential query on conditioned-tables we present a polynomial time algorithm solving the possible fact problem. We match this upper bound by two NP-completeness lower bounds, when the fixed query contains either negation or recursion and is applied to Codd-tables. Finally, we show that the certain fact problem is coNP-complete, even for a fixed first order query applied to a Codd-table.

TCS Journal 1986 Journal Article

Restructuring hierarchical database objects

• Serge Abiteboul
• Richard Hull

A class of hierarchical structures arising in Database Systems (complex objects) and Office Information Systems (forms) is studied. Two formalisms for restructuring are presented. The first focuses on a class of algebraic operators based on rewrite rules, and the second on structural transformations which preserve or augment data capacity. These transformations are related to a subclass of the rewrite operations which is closed under composition.