Programming Constructs for Unstructured Data

We investigate languages for querying and transforming unstructured data by which we mean languages than can be used without knowledge of the structure (schema) of the database. There are two reasons for wanting to do this. First, some data models have emerged in which the schema is either completely absent or only provides weak constraints on the data. Second, it is sometimes convenient, for the purposes of browsing, to query the database without reference to the schema. For example one may want to “grep” all character strings in the database, or one might want to find the information associated with a certain field name no matter where it occurs in the database. This paper introduces a labelled tree model of data and investigates various programming structures for querying and transforming such data. In particular, it considers various restrictions of structural recursion that give rise to well-de ned queries even when the input data contains cycles. It also discusses issues of observable equivalence of such structures.