Descriptive complexity theory for constraint databases

DOI10.1007/3-540-48168-0_6MaRDI QIDQ4945218zbMATH OpenFDO

Authors Erich Grädel, Stephan Kreutzer

Publication date 23 March 2000

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/3-540-48168-0_6

zbMATH Keywords

constraint databases

Mathematics Subject Classification ID

Database theory (68P15) Descriptive complexity and finite models (68Q19)

Recommendations

• scientific article; zbMATH DE number 1515857
• Queries with arithmetical constraints
• scientific article; zbMATH DE number 1515855
• The complexity of query evaluation in indefinite temporal constraint databases
• Query languages for real number databases based on descriptive complexity over R

Cited in

(12)

• The complexity of query evaluation in indefinite temporal constraint databases
• Average-case complexity for the execution of recursive definitions on relational databases (paper no 50-95 accepted for publication in ACTA INFORMATICA)
• Reachability and connectivity queries in constraint databases
• On the computational complexity of querying bounds on differences constraints
• Operational semantics for fixed-point logics on constraint databases
• scientific article; zbMATH DE number 1515857 (Why is no real title available?)
• Query languages for real number databases based on descriptive complexity over R
• Constraint Databases
• Tractability frontiers in probabilistic team semantics and existential second-order logic over the reals
• Tractability frontiers in probabilistic team semantics and existential second-order logic over the reals
• Linear constraint query languages expressive power and complexity
• An Ehrenfeucht-Fraïssé game approach to collapse results in database theory

This page was built for publication: Descriptive complexity theory for constraint databases

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4945218)