Concepts for modeling and querying list-structured data

摘要

Traditionally, data models and query languages have provided mechanisms for dealing with sets of objects. Many database applications, however, are list oriented (i.e., deal with collections or aggregates of objects in which ordering is important). This article presents the list-structure data model which has ordering as a fundamental feature. The model is based on atomic, aggregate, and list constructors and thus provides support for tree-structured and sequential representations of data. These constructors can be intermixed and allow the modeling of variable and recursive schemes. Such schemes occur naturally in list-oriented data like tagged text, dictionaries, genealogies, etc. The notion of patterns found in traditional text and list processing applications is generalized to deal with the tree-structured representation and then incorporated in operations for searching, marking, updating, and restructuring list-structure instances. These operations form the core of a query language wherein users can succinctly and naturally formulate complex problems typically encountered in list-oriented database applications.