A query language and optimization techniques for unstructured data

TLDR

A new data model has emerged in which databases are not constrained by a conventional schema, using tree‑like structures that can represent sets and tuples, offering great flexibility for data representation. The authors propose UnQL, a simple language for querying data organized as rooted, edge‑labeled graphs. UnQL represents relational data as fixed‑depth trees, is equivalent to relational algebra on such trees, introduces constructs for arbitrarily deep and cyclic structures, and supports efficient evaluation via vertical optimization for deep queries and horizontal optimization for flat‑relation operators. UnQL is strictly more powerful than path‑expression languages like XSQL yet remains efficiently evaluable.

Abstract

A new kind of data model has recently emerged in which the database is not constrained by a conventional schema. Systems like ACeDB, which has become very popular with biologists, and the recent Tsimmis proposal for data integration organize data in tree-like structures whose components can be used equally well to represent sets and tuples. Such structures allow great flexibility y in data representation.What query language is appropriate for such structures? Here we propose a simple language UnQL for querying data organized as a rooted, edge-labeled graph. In this model, relational data may be represented as fixed-depth trees, and on such trees UnQL is equivalent to the relational algebra. The novelty of UnQL consists in its programming constructs for arbitrarily deep data and for cyclic structures. While strictly more powerful than query languages with path expressions like XSQL, UnQL can still be efficiently evaluated. We describe new optimization techniques for the deep or "vertical" dimension of UnQL queries. Furthermore, we show that known optimization techniques for operators on flat relations apply to the "horizontal" dimension of UnQL.