This volume presents the proceedings of the 1995 International Conference on Database Theory, ICDT '95, held in Prague in January 1995.
Besides two full invited papers and the abstracts of two tutorials, the book includes the revised full versions of 29 technical contributions selected from a total of 116 submissions. The papers address all current aspects of database theory; they are organized in sections on optimization, nonmonotonic semantics, query languages, concurrency control, advanced models, probabilistic methods, constraints and dependencies, and Datalog analysis.
Author(s): Tomasz Imielinski (auth.), Georg Gottlob, Moshe Y. Vardi (eds.)
Series: Lecture Notes in Computer Science 893
Edition: 1
Publisher: Springer-Verlag Berlin Heidelberg
Year: 1995
Language: English
Pages: 460
Tags: Database Management; Computation by Abstract Devices; Mathematical Logic and Formal Languages; Artificial Intelligence (incl. Robotics)
Data on air — What's in it for the database theorist....Pages 1-13
Spatial databases, The final frontier....Pages 14-32
Tutorial on parallel database systems....Pages 33-37
Languages for polynomial-time queries — An ongoing quest....Pages 38-39
Distributed query optimization in loosely coupled multidatabase systems....Pages 40-53
On the complexity of generating optimal left-deep processing trees with cross products....Pages 54-67
Querying disjunctive databases through nonmonotonic logics....Pages 68-81
DATALOG queries with stratified negation and choice: from P to D P ....Pages 82-96
On the Kolmogorov expressive power of boolean query languages....Pages 97-110
On two forms of structural recursion....Pages 111-124
Δ -Languages for sets and sub-PTIME graph transformers....Pages 125-138
Partial strictness in two-phase locking....Pages 139-147
Unified transaction model for semantically rich operations....Pages 148-161
The Dynamic Two Phase Commitment (D2PC) protocol....Pages 162-176
Domain-independent queries on databases with external functions....Pages 177-190
An algebra for pomsets....Pages 191-207
On the power of stratified logic programs with value invention for expressing database transformations....Pages 208-221
A stable model semantics for behavioral inheritance in deductive object oriented languages....Pages 222-237
A rewriting technique for the analysis and the optimization of active databases....Pages 238-251
Sorted HiLog: Sorts in higher-order logic data languages....Pages 252-265
The average length of keys and functional dependencies in (random) databases....Pages 266-279
Uniformly-distributed random generation of join orders....Pages 280-293
A probabilistic view of Datalog parallelization....Pages 294-307
A first step towards implementing dynamic algebraic dependencies....Pages 308-321
Constraint-generating dependencies....Pages 322-337
Optimization using tuple subsumption....Pages 338-352
Dterministic and non-deterministic stable model semantics for unbound DATALOG queries....Pages 353-367
Revision programming, database updates and integrity constraints....Pages 368-382
Some positive results for boundedness of multiple recursive rules....Pages 383-396
Increment boundedness and nonrecursive incremental evaluation of datalog queries....Pages 397-410
Approximation in databases....Pages 411-424
Datalog queries of set constraint databases....Pages 425-438
Space usage in functional query languages....Pages 439-454
