Domain independence and the relational calculus
Several alternative semantics (or interpretations) of the relational (domain) calculus are studied here. It is shown that they all have the same expressive power, i.e., the selection of any of the semantics neither gains nor loses expressive power. Since the domain is potentially infinite, the answer to a relational calculus query is sometimes infinite (and hence not a relational). The following approaches which guarantee the finiteness of answers to queries are studied here: output-restricted unlimited interpretation, domain independental queries, output-restricted finite and countable invention, and limited interpretation. Of particular interest is the output- restricted unlimited interpretation -- although the output is restricted to the active domain of the input and query, the quantified variables range over the infinite underlying domain. While this is close to the intuitive interpretation given to calculus formulas, the naive approach to evaluating queries under this semantics calls for the impossible task of examining infinitely many values. We describe here a construction which, given a query \(Q\) under the output-restricted unlimited interpretation, yields a domain independent query \(Q'\), with length no more than exponential in the length of \(Q\), such that \(Q\) and \(Q'\) (under their respective semantics) express the same function.
- scientific article; zbMATH DE number 4064539
- scientific article; zbMATH DE number 4049009
- Relational calculus for actionable knowledge
- Equivalence of the relational algebra and calculus for nested relations
- Domain-independent formulas and databases
- Independence logic and abstract independence relations
- Relational Parametricity and Separation Logic
- Relational Parametricity and Separation Logic
- Semantics of a relational \(\lambda\)-calculus
- scientific article; zbMATH DE number 1735907
- A relational model of data for large shared data banks
- Computable queries for relational data bases
- Horn clauses and database dependencies
- scientific article; zbMATH DE number 3823168 (Why is no real title available?)
- On the expressive power of database queries with intermediate types
- Relative Information Capacity of Simple Relational Database Schemata
- Safety, domain independence and translation of complex value database queries
- Domain-independent formulas and databases
- On the expressive power of database queries with intermediate types
- Relative consistency and accessible domains
- The expressive power of stratified logic programs with value invention
- Query languages for bags and aggregate functions
- Finitely representable databases
- Reasoning about strings in databases
- Finite queries do not have effective syntax.
- Relational calculus for actionable knowledge
- SHACL: a description logic in disguise
- scientific article; zbMATH DE number 4199657 (Why is no real title available?)
- Combining Consistency and Confidentiality Requirements in First-Order Databases
- scientific article; zbMATH DE number 4064539 (Why is no real title available?)
- Syntactical characterization of a subset of domain-independent formulas
- Stability theory, permutations of indiscernibles, and embedded finite models
- scientific article; zbMATH DE number 219206 (Why is no real title available?)
- A sound and complete model-generation procedure for consistent and confidentiality-preserving databases
- Efficient Evaluation of Arbitrary Relational Calculus Queries
- Expressiveness of SHACL Features and Extensions for Full Equality and Disjointness Tests
- The past and future of embedded finite model theory
- A closed-form evaluation for Datalog queries with integer (gap)-order constraints
This page was built for publication: Domain independence and the relational calculus
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1338897)
