Key points are not available for this paper at this time.
Two complexity measures for query languages are proposed. Data complexity is the complexity of evaluating a query in the language as a function of the size of the database, and expression complexity is the complexity of ewduating a query in the language as a function of the size of the expression defining the query. We study the data and expression complexity of logical langnages- relational calculus and its extensions by transitive closure, fixpoint and second order existential quantification- and algebraic languages- relational algebra and its extensions by bounded and unbounded looping. The pattern which will bc shown is that the expression complexity of the investi-gated languages is one exponential higher then their data complexity, and for both types of complexity we show completeness in some complexity class. Research supported by a Weizrnann Post-doctoral Fellowship,
Moshe Y. Vardi (Fri,) studied this question.
Synapse has enriched 5 closely related papers on similar clinical questions. Consider them for comparative context: