Structure and complexity of relational queries

DOI10.1016/0022-0000(82)90012-5zbMath0511.68073OpenAlexW1984890936MaRDI QIDQ1838840

Publication date: 1982

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0022-0000(82)90012-5

zbMATH Keywords

computational complexity relational database expressiveness logical queries algebraic queries queries languages

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Model theory of finite structures (03C13) Data structures (68P05) Information storage and retrieval of data (68P20)

Related Items (only showing first 100 items - show all)

Finite Variable Logics in Descriptive Complexity Theory ⋮ Expressive power and succinctness of the positive calculus of binary relations ⋮ Generalized quantifiers and pebble games on finite structures ⋮ Multiple total stable models are definitely needed to solve unique solution problems ⋮ Parallel complexity of logical query programs ⋮ Non-determinism in logic-based languages ⋮ Canonization for two variables and puzzles on the square ⋮ The expressive powers of stable models for bound and unbound DATALOG queries ⋮ Directions in generalized quantifier theory ⋮ Role of determinism in query languages for data bases ⋮ The complexity of query evaluation in indefinite temporal constraint databases ⋮ Computable functions in tabular databases ⋮ How to define a linear order on finite models ⋮ European Summer Meeting of the Association for Symbolic Logic, (Logic Colloquium '87), Granada, Spain, 1987 ⋮ Dyn-FO: A parallel, dynamic complexity class ⋮ Query languages for bags and aggregate functions ⋮ Finitely representable databases ⋮ The expressive power of unique total stable model semantics ⋮ Hierarchies in transitive closure logic, stratified Datalog and infinitary logic ⋮ Polynomial-time computable stable models ⋮ An alternative way to represent the cogroup of a relation in the context of nested databases ⋮ Circumscribing DATALOG: expressive power and complexity ⋮ Meeting of the Association for Symbolic Logic, Stanford, California, 1985 ⋮ Complexity and undecidability results for logic programming ⋮ Reachability is harder for directed than for undirected finite graphs ⋮ Bounds for the Quantifier Depth in Finite-Variable Logics ⋮ A probabilistic view of Datalog parallelization ⋮ Queries with arithmetical constraints ⋮ Bounded fixpoints for complex objects ⋮ Semantics and complexity of abduction from default theories ⋮ On the Descriptive Complexity of Linear Algebra ⋮ Classifying the computational complexity of problems ⋮ First-order spectra with one variable ⋮ A note on fixpoint techniques in data base recursive logic programs ⋮ Bisimulation-invariant PTIME and higher-dimensional \(\mu\)-calculus ⋮ 0-1 laws and decision problems for fragments of second-order logic ⋮ On the representation and querying of sets of possible worlds ⋮ Infinitary logics and very sparse random graphs ⋮ Datalog extensions for database queries and updates ⋮ Why not negation by fixpoint? ⋮ On the expressive power of database queries with intermediate types ⋮ Computing on structures ⋮ A comparison between algebraic query languages for flat and nested databases ⋮ An analysis of the Core-ML language: Expressive power and type reconstruction ⋮ An analysis of fixed-point queries on binary trees ⋮ The expressive power of the bounded-iteration construct ⋮ The expressiveness of a family of finite set languages ⋮ Principles of programming with complex objects and collection types ⋮ Computing with infinitary logic ⋮ A simple proof on the decidability of equivalence between recursive and nonrecursive Datalog programs ⋮ On the equivalence of recursive and nonrecursive Datalog programs ⋮ Knowledgebase transformations ⋮ Reusing and modifying rulebases by predicate substitution ⋮ The invariant problem for binary string structures and the parallel complexity theory of queries ⋮ Equivalence of the relational algebra and calculus for nested relations ⋮ Unnamed Item ⋮ Implicit definability and infinitary logic in finite model theory ⋮ Capturing complexity classes by fragments of second-order logic ⋮ The functional dimension of inductive definitions ⋮ Infinitary logics and 0-1 laws ⋮ The powerset algebra as a natural tool to handle nested database relations ⋮ Algebraic and calculus query languages for recursively typed complex objects ⋮ The alternating fixpoint of logic programs with negation ⋮ Finite-model theory -- A personal perspective ⋮ On the complexity of queries in the logical data model ⋮ Query languages for hierarchic databases ⋮ The parallel complexity of single rule logic programs ⋮ An optimal lower bound on the number of variables for graph identification ⋮ Number of variables is equivalent to space ⋮ The Evaluation and the Computational Complexity of Datalog Queries of Boolean Constraint Databases ⋮ Database Theory, Yuri, and Me ⋮ On Complete Problems, Relativizations and Logics for Complexity Classes ⋮ A Logic for PTIME and a Parameterized Halting Problem ⋮ Fixed-Point Definability and Polynomial Time on Chordal Graphs and Line Graphs ⋮ Choiceless Computation and Symmetry ⋮ Querying logical databases ⋮ Comparison of expressive power of some query languages for databases ⋮ Recursive query processing: The power of logic ⋮ Bounds in the propagation of selection into logic programs ⋮ Negation in rule-based database languages: A survey ⋮ On winning strategies in Ehrenfeucht-Fraïssé games ⋮ Logical Foundations of XML and XQuery ⋮ An extension of fixpoint logic with a symmetry-based choice construct ⋮ Reflective relational machines ⋮ A restricted second order logic for finite structures ⋮ Expressive power and complexity of partial models for disjunctive deductive databases ⋮ Fixed-Point Definability and Polynomial Time ⋮ Arity bounds in first-order incremental evaluation and definition of polynomial time database queries ⋮ Fixpoint strategies for deductive databases ⋮ Arity hierarchies ⋮ Almost Everywhere Equivalence of Logics in Finite Model Theory ⋮ A generalized closure and complement phenomenon ⋮ Complexity and expressive power of deterministic semantics for DATALOG\(^ \neg\). ⋮ Adding for-loops to first-order logic ⋮ Hereditarily-finite sets, data bases and polynomial-time computability ⋮ The expressive power of stratified logic programs ⋮ Functional queries in datalog ⋮ Program schemes, arrays, Lindström quantifiers and zero-one laws ⋮ Some thoughts on computational models: from massive human computing to abstract state machines, and beyond ⋮ Computation on structures. Behavioural theory, logic, complexity

Cites Work

This page was built for publication: Structure and complexity of relational queries