Finitely representable nested relations

Advanced temporal and spatial applications require both the representation of complex objects and the ability to finitely represent infinite relations. Representing such data requires combining the constraint relational model (allowing finite representation of infinite information) and either the nested relational or the object-oriented model (allowing representation of complex objects). In this paper, we extend the nested relational calculus to deal with finitely representable relations. The aim of the language we propose, called frNRC, is to provide the right formal foundations to analyze nested constraint query languages, overcoming some limitations of already existing languages. As an example of the theoretical foundations of frNRC, we show that it is effectively computable and has low data complexity. Moreover, frNRC queries are independent of the depth of set nesting in data generated by intermediate computations. (C) 1999 Published by Elsevier Science B.V. All rights reserved.