We address the problem of query rewriting and query answering using views in the context of semi-structured data. We present a method for computing the rewriting of a regular expression E in terms of other regular expressions. The method computes the exact rewriting (the one that defines the same regular language as E) if it exists, or the rewriting that defines the maximal language contained in the one defined by E, otherwise. We present a complexity analysis of both the problem and the method, showing the latter is essentially optimal. Finally, we illustrate how to exploit the above mentioned method in order to devise an algorithm for rewriting regular path queries and for answering such queries for semi-structured data using views.

Biography

Maurizio Lenzerini is a professor of Computer Science at the Universita` di Roma "La Sapienza", was born in Pavia, on December 14, 1954. He graduated in Computer Engineering at the University of Rome "La Sapienza" in 1980. Since 1983 he teaches courses in Computer Science at Italian universities. From 1983 to 1987 he was assistant professor, from 1987 to 1990 he was associate professor, at Universita` di Roma "La Sapienza", where he is now a full professor and Director of the Diploma di Ingegneria Informatica ed Automatica

His main research interests are in the areas of Databases and Knowledge Representation and Reasoning. In particular, in the area of Databases, he is interested in conceptual and semantic data models, database integration, data warehouses, deductive and object-oriented databases, semistructured data. In the area of Knowledge Representation and Reasoning, his interest focuses on taxonomic and description logics, nonmonotonic reasoning, and the computational complexity of various forms of reasoning. He is author of more than hundred publications on these topics.

In the last decade, within the Dipartimento di Informatica e Sistemistica of the University of Rome "La Sapienza", he has been coordinating a research team working on Artificial Intelligence and Databases. Projects in his group investigate the foundations of Knowledge Representation techniques and their applications to conceptual database modeling, cooperative information systems, data warehouses.

Prof. Maurizio Lenzerini's visit to Bilkent is partially supported by TUBITAK.