𝔖 Bobbio Scriptorium
✦   LIBER   ✦

The complexity of satisfying constraints on databases of transactions

✍ Scribed by Toon Calders

Publisher
Springer-Verlag
Year
2007
Tongue
English
Weight
515 KB
Volume
44
Category
Article
ISSN
0001-5903

No coin nor oath required. For personal study only.

πŸ“œ SIMILAR VOLUMES

On the computational complexity of query
On the computational complexity of querying bounds on differences constraints
✍ Vittorio Brusoni; Luca Console; Paolo Terenziani πŸ“‚ Article πŸ“… 1995 πŸ› Elsevier Science 🌐 English βš– 891 KB

Given a consistent knowledge base formed by a set of constraints, efficient query answering (e.g., checking whether a set of constraints is consistent with the knowledge base or necessarily true in it) is practically very important. In the paper we consider bounds on differences (which are an import

On the Complexity of Database Queries
On the Complexity of Database Queries
✍ Christos H. Papadimitriou; Mihalis Yannakakis πŸ“‚ Article πŸ“… 1999 πŸ› Elsevier Science 🌐 English βš– 223 KB

We revisit the issue of the complexity of database queries, in the light of the recent parametric refinement of complexity theory. We show that, if the query size (or the number of variables in the query) is considered as a parameter, then the relational calculus and its fragments (conjunctive queri