The complexity of higher-order queries

DOI10.1016/J.IC.2015.07.003MaRDI QIDQ498405zbMATH OpenOpenAlexFDO

Authors Michael Benedikt, Gabriele Puppis, Huy Vu

Publication date 28 September 2015

Published in Information and Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.ic.2015.07.003

Mathematics Subject Classification ID

Database theory (68P15)

Recommendations

• The expressive power of higher-order Datalog
• On the efficiency of transforming database logic programs
• Query languages for hierarchic databases
• Decidable containment of recursive queries
• scientific article; zbMATH DE number 4064541

Cites work

• scientific article; zbMATH DE number 1722667 (Why is no real title available?)
• scientific article; zbMATH DE number 2086292 (Why is no real title available?)
• scientific article; zbMATH DE number 42059 (Why is no real title available?)
• scientific article; zbMATH DE number 3607517 (Why is no real title available?)
• scientific article; zbMATH DE number 1324669 (Why is no real title available?)
• scientific article; zbMATH DE number 839556 (Why is no real title available?)
• scientific article; zbMATH DE number 5239554 (Why is no real title available?)
• A simple proof of a theorem of Statman
• A theory of type polymorphism in programming
• Answering queries using limited external query processors
• Conjunctive query containment over trees
• Database Theory - ICDT 2005
• Database query languages embedded in the typed lambda calculus
• Eliminating definitions and Skolem functions in first-order logic
• Equivalences Among Relational Expressions with the Union and Difference Operators
• Expressive capabilities description languages and query rewriting algorithms
• HiLog: A foundation for higher-order logic programming
• Inclusion dependencies and their interaction with functional dependencies
• On negation in Hilog
• On the complexity of single-rule datalog queries.
• On the expressive power of the relational algebra
• Polymorphic type inference for the relational algebra
• Querying data sources that export infinite sets of views
• Relational queries computable in polynomial time
• Testing containment of conjunctive queries under functional and inclusion dependencies
• The typed lambda-calculus is not elementary recursive
• Typed query languages for databases containing queries
• Well-definedness and semantic type-checking for the nested relational calculus

Cited in

(9)

• On the Computational Power of Querying the History
• The query complexity of order-finding
• scientific article; zbMATH DE number 4058873 (Why is no real title available?)
• Query order in the polynomial hierarchy
• Approximate Query Complexity
• Strongly-Normalizing Higher-Order Relational Queries
• Nesting Depth of Operators in Graph Database Queries: Expressiveness Vs. Evaluation Complexity
• The query complexity of certification
• scientific article; zbMATH DE number 4064541 (Why is no real title available?)

Describes a project that uses

Uses Software

• Links
• Kleisli
• XQuery
• HiLog
• ML

This page was built for publication: The complexity of higher-order queries

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