Title: Fixpoints and Bounded Fixpoints for Complex Objects
Abstract:We investigate a query language for complex-object databases, which is designed to (1) express only tractable queries, and (2) be as expressive over flat relations as first order logic with fixpoints....We investigate a query language for complex-object databases, which is designed to (1) express only tractable queries, and (2) be as expressive over flat relations as first order logic with fixpoints. The language is obtained by extending the relational algebra NRA with a fixpoint operator. As in the flat case, all PTime computable queries over ordered databases are expressible in this language. The main result consists in proving that this language is a conservative extension of the first order logic with fixpoints, or of the whilequeries (depending on the interpretation of the bounded fixpoint: inflationary or partial). The proof technique uses indexes, to encode complex objects into flat relations, and is strong enough to allow for the encoding of NRA with unbounded fixpoints into flat relations. We also define a logic based language with fixpoints, the nested relational calculus, and prove that its range restricted version is equivalent to NRA with bounded fixpoints. Comments University of Pennsylvania Department of Computer and Information Science Technical Report No. MSCIS-93-32. This technical report is available at ScholarlyCommons: http://repository.upenn.edu/cis_reports/283 Fixpoints and Bounded Fixpoints for Complex Objects Dan Suciu * Department of Computer and Information Science University of Pennsylvania Philadelphia, PA 19104-6389 Email: [email protected]Read More
Publication Year: 1993
Publication Date: 1993-01-01
Language: en
Type: article
Access and Citation
Cited By Count: 18
AI Researcher Chatbot
Get quick answers to your questions about the article from our AI researcher chatbot