Optimal implementation of conjunctive queries in relational data bases
Explore this paper's citation graph
Summary
It is shown that while answering conjunctive queries is NP complete (general queries are PSPACE complete), one can find an implementation that is within a constant of optimal.
- Type
- article
- Published
- 1977-05-04
- Cited by
- 1,448
- References
- 24
- Access
- Open access
- OpenAlex
- https://openalex.org/W1979514837
- Semantic Scholar
- https://api.semanticscholar.org/CorpusID:334870
Keywords
Conjunctive query, Boolean conjunctive query, Computer science, Class (philosophy), Relational database
References
- Implementation of Relational Data Base Management Systems (NCC 1975 Panel)
- Relational Model for a Data Base
- Relational Completeness of Data Base Sublanguages
- The relational and network approaches: Comparison of the application programming interfaces
- Complexity of finitely presented algebras
- Unacceptable file operations in a relational data base
- SEQUEL: A structured English query language
- Optimizing the performance of a relational algebra database interface
- Designing optimal data structures
- Gaussian elimination is not optimal
- Concepts of a Data Independent Accessing Model
- Evaluating inter-entry retrieval expressions in a relational data base management system
- Specifying queries as relational expressions
- A data base sublanguage founded on the relational calculus
- Computing joins of relations
- RISS: a generalized minicomputer relational data base management system
- A psychological study of query by example
- The Peterlee Relational Test Vehicle - A System Overview
- INGRES: a relational data base system
- A multi-level relational system
Cited by
- Towards automated reformulation of specications
- Combining Heterogeneous Data Sources through Query Correspondence Assertions
- The complexity of querying indefinite information: defined relations, recursion and linear order
- View -based rewriting algorithms for conjunctive queries with arithmetic comparisons
- Data Integration under the Schema Tuple Query Assumption
- Conjunctive Query Containment in the Presence of Disjunctive Integrity Constraints
- Inheritance As a Primitive Of Conceptual Modeling
- Constraint satisfaction, databases, and logic
- Provenance in collaborative data sharing
- View-Based techniques for the efficient management of web data. (Techniques fondées sur des vues matérialisées pour la gestion efficace des données du web)
- On the Compilability of Diagnosis, Planning, Reasoning about Actions, Belief Revision, etc
- Contención de consultas con valores nulos usando el método CQC
- Verification of Knowledge Bases: a Unifying Logical View
- Containment of inequality queries revisited
- Logical Form and Knowledge Representation: towards a reconciliation
- Abe: A Query Language for Constructing Aggregates-by-Example
- Selecting and Using Views to Compute Aggregate Queries (Extended Abstract)
- Update Relevance under the Multiset Semantics of RDBMS
- Conjunctive Queries for EL with Composition of Roles
- Feeding a data warehouse with data coming from web services. A mediation approach for the DaWeS prototype. (Alimenter un entrepôt de données par des données issues de services web. Une approche médiation pour le prototype DaWeS)
Related papers
- Containment and minimization of positive conjunctive queries in OODB's
- The complexity of acyclic conjunctive queries
- Generalized Deletion Propagation on Counting Conjunctive Query Answers
- Conjunctive Query Answering for Description Logics with Transitive Roles
- The dichotomy of conjunctive queries on probabilistic structures
- Conjunctive Query Entailment for SHOQ
- A Trichotomy in the Data Complexity of Certain Query Answering for Conjunctive Queries
- Conjunctive queries over trees