Combinatorial Games In Database Theory.

@inproceedings{DBLP:conf/pods/Kolaitis95,
  author    = {Phokion G. Kolaitis},
  title     = {Combinatorial Games In Database Theory},
  booktitle = {Proceedings of the Fourteenth ACM SIGACT-SIGMOD-SIGART Symposium
               on Principles of Database Systems, May 22-25, 1995, San Jose,
               California},
  publisher = {ACM Press},
  year      = {1995},
  isbn      = {0-89791-730-8},
  pages     = {231-232},
  ee        = {http://doi.acm.org/10.1145/212433.212461, db/conf/pods/Kolaitis95.html},
  crossref  = {DBLP:conf/pods/95},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

During the past fifteen years, the study of rule-based query languages has occupied a prominent place in database theory. Much of the work in this area has been devoted to a comprehensive investigation of the expressive power of such query languages. In carrying out this investigation, researchers have relied heavily on the method of combinatorial games, a versatile method that originated in classical mathematical logic and became quite indispensable in finite model theory.

The aim of this tutorial is to present the main combinatorial games used in database theory, give a representative sample of their numerous applications, but also indicate some of their limitations. In particular, the tutorial will cover Ehrenfeucht-Fraissé games, games for monadic NP, and pebble games. Moreover, it will illustrate the use of these games in relational calculus, Datalog, and fixpoint logic.

Below is a partial list of references for the main results presented in this tutorial.

Copyright © 1995 by the ACM, Inc., used by permission. Permission to make digital or hard copies is granted provided that copies are not made or distributed for profit or direct commercial advantage, and that copies show this notice on the first page or initial screen of a display along with the full citation.

• Windows: Click the letter of your CD drive
  A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
• UNIX/LINUX/Mac: use mount point /pods8298/... or /cdrom/...

• Windows: Click the letter of your CD drive
  A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
• UNIX/LINUX/Mac: use mount point /aDVD1/... or /cdrom/...

Printed Edition

Online Edition: ACM Digital Library

References

[1]

Foto N. Afrati, Stavros S. Cosmadakis, Mihalis Yannakakis: On Datalog vs. Polynomial Time. PODS 1991: 13-25 BibTeX

[2]

Alfred V. Aho, Jeffrey D. Ullman: The Universality of Data Retrieval Languages. POPL 1979: 110-120 BibTeX

[3]

...

[4]

...

[5]

Catriel Beeri, Paris C. Kanellakis, François Bancilhon, Raghu Ramakrishnan: Bounds on the Propagation of Selection into Logic Programs. PODS 1987: 214-226 BibTeX

[6]

...

[7]

Ashok K. Chandra: Theory of Database Queries. PODS 1988: 1-9 BibTeX

[8]

Ashok K. Chandra, David Harel: Computable Queries for Relational Data Bases. J. Comput. Syst. Sci. 21(2): 156-178(1980) BibTeX

[9]

Ashok K. Chandra, David Harel: Structure and Complexity of Relational Queries. J. Comput. Syst. Sci. 25(1): 99-128(1982) BibTeX

[10]

Surajit Chaudhuri, Phokion G. Kolaitis: Can Datalog be Approximated? PODS 1994: 86-96 BibTeX

[11]

...

[12]

...

[13]

Michel de Rougemont: Uniform Definability on Finite Structures with Successor. STOC 1984: 409-417 BibTeX

[14]

...

[15]

...

[16]

Ronald Fagin: Finite-Model Theory - A Personal Perspective. Theor. Comput. Sci. 116(1&2): 3-31(1993) BibTeX

[17]

...

[18]

...

[19]

...

[20]

...

[21]

...

[22]

Lauri Hella: Logical Hierarchies in PTIME. LICS 1992: 360-368 BibTeX

[23]

Neil Immerman: Number of Quantifiers is Better Than Number of Tape Cells. J. Comput. Syst. Sci. 22(3): 384-406(1981) BibTeX

[24]

Neil Immerman: Upper and Lower Bounds for First Order Expressibility. J. Comput. Syst. Sci. 25(1): 76-98(1982) BibTeX

[25]

Neil Immerman, Dexter Kozen: Definability with Bounded Number of Bound Variables. Inf. Comput. 83(2): 121-139(1989) BibTeX

[26]

...

[27]

Phokion G. Kolaitis: The Expressive Power of Stratified Programs. Inf. Comput. 90(1): 50-66(1991) BibTeX

[28]

Phokion G. Kolaitis, Moshe Y. Vardi: On the Expressive Power of Datalog: Tools and a Case Study. J. Comput. Syst. Sci. 51(1): 110-134(1995) BibTeX

[29]

Phokion G. Kolaitis, Moshe Y. Vardi: Infinitary Logics and 0-1 Laws. Inf. Comput. 98(2): 258-294(1992) BibTeX

[30]

V. S. Lakshmanan, Alberto O. Mendelzon: Inductive Pebble Games and the Expressive Power of Datalog. PODS 1989: 301-310 BibTeX

[31]

...