SQL4X: A flexible query language for XML and relational databases

SQL4X, a powerful language for simultaneously querying both relational and XML databases is presented. Using SQL4X, one can create both relations and XML documents as query results. Thus, SQL4X can be thought of as an integration language. In order to allow easy integration of XML documents with varied structures, SQL4X uses flexible semantics when querying XML. SQL4X is also a powerful query language. It can express quantification, negation, aggregation, grouping and path expressions. Datalog(4x) and Tree-Datalog(4x), extensions of Datalog, are defined as elegant abstract models for SQL4X queries. Query containment is characterized for many common classes of SQL4X queries. Specifically, for Datalog(4x) queries, a complete characterization of containment of conjunctive queries and of unions of queries is presented. Equivalence of Datalog(4x) queries under bag-set semantics is also characterized. A sufficient condition for containment of Tree-Datalog(4x) queries is presented. This condition is shown to be complete for a large class of common queries..