call for papers attracted 116 submissions. The nine papers in this special issue were selected from the thirty-two papers presented in Philadelphia. Their authors were invited to submit more complete and revised versions for this issue for a round of careful refereeing.
The paper titled ''Tracking Join and Self-Join Sizes in Limited Storage,'' by Alon, Gibbons, Matias, and Szegedy, examines the problem of incrementally approximating the size of join and self-join results when storage is limited. It presents several algorithms, accompanied by both theoretical and experimental results.
''A Framework for Measuring Differences in Data Characteristics,'' by Ganti, Gehrke, Ramakrishnan, and Loh, provides a framework and algorithms to measure differences between data sets with respect to the data-mining models they induce. Its approach is quite general and captures several types of models as well as several measures of difference.
The paper ''Maximizing Sharing of Protected Information,'' by Dawson, De Capitani Di Vimercati, Lincoln, and Samarati, deals with the issue of security in database systems, and particularly with the issue of preventing sensitive information from leaking to the outside. It contains an approach that classifies information at the desired level and enforces constraints on what a user may derive through inference or data associations.
In ''Aggregate Operators in Constraint Query Languages,'' Benedikt and Libkin extend constraint query languages with both standard and spatial aggregate operators, including approximate operators. They present several results regarding expressiveness and closure of such extended languages.
''Querying Incomplete Information in Semistructured Data,'' by Kanza, Nutt, and Sagiv, considers queries on semistructured data (as in xml) which admit incomplete (i.e., not fully instantiated) answers. The authors tackle the difficulties and choices in defining the semantics of such queries, and they develop algorithms for them.
Semistructured data are also the subject of ''Rewriting of Regular Expressions and Regular Path Queries,'' by Calvanese, De Giacomo, Lenzerini, and Vardi. They address the problem of rewriting regular-expression (path) queries in the context of semi-structured data, and provide a method that modifies such a query and generates an optimal rewriting based on a collection of available views.
In the paper ''Inherent Complexity of Recursive Queries,'' Cosmadakis points out the limitations of Datalog optimisations by proving lower bounds on the