Theory of Computing Systems

Editor’s Note: Special Issue on Database Theory

Optimal Probabilistic Generation of XML Documents

Serge Abiteboul, Yael Amsterdamer, Daniel Deutch, Tova Milo, P. Senellart

On the Data Complexity of Consistent Query Answering

Balder ten Cate, Gaëlle Fontaine, Phokion G. Kolaitis

Certain Answers over Incomplete XML Documents: Extending Tractability Boundary

Amélie Gheerbrant, Leonid Libkin

Highly Expressive Query Languages for Unordered Data Trees

Serge Abiteboul, Pierre Bourhis, Victor Vianu

Deciding Twig-definability of Node Selecting Tree Automata

Timos Antonopoulos, Dag Hovland, Wim Martens, Frank Neven

Parallel Skyline Queries

Foto N. Afrati, Paraschos Koutris, Dan Suciu, Jeffrey D. Ullman

Deciding Confluence for a Simple Class of Relational Transducer Networks

Tom J. Ameloot, Jan Van den Bussche

Foreword: Special Issue on Database Theory

Balder ten Cate, Wang-Chiew Tan

Fast Learning of Restricted Regular Expressions and DTDs

Dominik D. Freydenberger, Timo Kötzing

Lower Bounds on the Error of Query Sets Under the Differentially-Private Matrix Mechanism

Chao Li, Gerome Miklau

Structural Tractability of Counting of Solutions to Conjunctive Queries

Arnaud Durand, Stefan Mengel

Which XML Schemas are Streaming Bounded Repairable?

Pierre Bourhis, Gabriele Puppis, Cristian Riveros

XML Compression via Directed Acyclic Graphs

Mireille Bousquet-Mélou, Markus Lohrey, Sebastian Maneth, Eric Noeth