Welcome to D
SIGMOD'00
PODS'00
= PODS'00 Webs
= Plenary Talk
<<< = PODS'00 Pape>>>
SIGMOD Recor
CIKM 2000/CI
COMAD 2000
Data Enginee
DL 2000
DPDJ
EDBT 2000
Hypertext 20
ICDE 2000
KDD 2000
KDD Explorat
KRDB 2000
SBBD 2000
SIGIR 2000
SIGIR Forum
SSDBM 2000
TODS
VLDB'00
VLDBJ

Fixed-Point Query Languages for Linear Constraint Databases


Stephan Kreutzer

  View Paper (PDF)  

Return to Spatial and Constraint Databases


Abstract

We introduce a family of query languages for linear constraint databases over the reals. The languages are defined over two-sorted structures, the first sort being the real numbers and the second sort consisting of a decomposition of the input relation into regions. The languages are defined as extensions of first-order logic by transitive closure or fixed-point operators, where the fixed-point operators are defined over the set of regions only. It is shown that the query languages capture precisely the queries definable in various standard complexity classes including PTIME.


References


Note: References link to DBLP on the Web.

[1]
Richard Anderson , Paul Beame , Erik Brisson : Parallel Algorithms for Arrangements. Algorithmica 15(2) : 104-125(1996)
[2]
Freddy Dumortier , Marc Gyssens , Luc Vandeurzen , Dirk Van Gucht : On the Decidability of Semi-Linearity of Semi-Algebraic Sets and Its Implications for Spatial Databases. PODS 1997 : 68-77
[3]
...
[4]
...
[5]
...
[6]
...
[7]
...
[8]
Erich Grädel , Yuri Gurevich : Metafinite Model Theory. Information and Computation 140(1) : 26-81(1998)
[9]
Erich Grädel , Stephan Kreutzer : Descriptive Complexity Theory for Constraint Databases. CSL 1999 : 67-81
[10]
...
[11]
Stéphane Grumbach , Gabriel M. Kuper : Tractable Recursion over Geometric Data. CP 1997 : 450-462
[12]
Stéphane Grumbach , Jianwen Su : Finitely Representable Databases. JCSS 55(2) : 273-298(1997)
[13]
Stéphane Grumbach , Jianwen Su : Queries with Arithmetical Constraints. TCS 173(1) : 151-181(1997)
[14]
David Harel : Towards a Theory of Recursive Structures. MFCS 1998 : 36-53
[15]
...
[16]
Paris C. Kanellakis , Gabriel M. Kuper , Peter Z. Revesz : Constraint Query Languages. JCSS 51(1) : 26-52(1995)
[17]
Paris C. Kanellakis , Gabriel M. Kuper , Peter Z. Revesz : Constraint Query Languages. PODS 1990 : 299-313
[18]
Bart Kuijpers , Jan Paredaens , Marc Smits , Jan Van den Bussche : Termination Properties of Spatial Datalog Programs. Logic in Databases 1996 : 101-116
[19]
Gabriel M. Kuper , Leonid Libkin , Jan Paredaens : Introduction. Constraint Databases 2000 : 1-16
[20]
...
[21]
Luc Vandeurzen , Marc Gyssens , Dirk Van Gucht : On the Desirability and Limitations of Linear Spatial Database Models. SSD 1995 : 14-28
[22]
Luc Vandeurzen , Marc Gyssens , Dirk Van Gucht : On Query Languages for Linear Queries Definable with Polynomial Constraints. CP 1996 : 468-481
[23]
...

Referenced by

  1. Jan Van den Bussche : Constraint databases: A tutorial introduction. SIGMOD Record 29(3) : 44-51(2000)

BIBTEX


@inproceedings{DBLP:conf/pods/Kreutzer00,
  author    = {Stephan Kreutzer},
   title     = {Fixed-Point Query Languages for Linear Constraint Databases},
   booktitle = {Proceedings of the Nineteenth ACM SIGMOD-SIGACT-SIGART Symposium
                on Principles of Database Systems, May 15-17, 2000, Dallas, Texas,
                USA},
   publisher = {ACM},
   year      = {2000},
   isbn      = {1-58113-214-X},
   pages     = {116-125},
   crossref  = {DBLP:conf/pods/00},
   bibsource = {DBLP, http://dblp.uni-trier.de} } },


DiSC'01 Copyright ©2002 ACM Inc.