Detecting common subexpressions for multiple query optimization over loosely-coupled heterogeneous data sources

Mahesh B. Chaudhari, Suzanne Dietrich

Research output: Contribution to journalArticlepeer-review

8 Scopus citations


The research presented in this paper supports the identification of common subexpressions as candidates for potential materialized views that form the basis of multiple query optimization in a loosely-coupled distributed system where query expressions access heterogeneous data sources, including relations and data-centric XML. This paper introduces a unifying mixed multigraph formalism to represent SQL, XQuery, and LINQ queries in a common query graph model and a heuristics-based algorithm to detect common subexpressions. The identified common subexpressions represent an opportunity for defining a materialized view to avoid repeating computation. The common subexpressions may access only relations, only XML, or a combination of relations and XML. The mixed multigraph model and the heuristic rules presented in this paper have distinguished advantages over the existing approaches that consider only relational or XML data sources individually. The mixed multigraph model can present SQL, XQuery, and LINQ queries in a single graph model and the heuristic rules are designed to consider the identical and subsumed conditions at the same time. A prototype implementation of the algorithm illustrates the applicability of the approach using various examples from the research literature as well as scenarios over a Criminal Justice enterprise that include common subexpressions across relational and XML data sources.

Original languageEnglish (US)
Pages (from-to)119-143
Number of pages25
JournalDistributed and Parallel Databases
Issue number2
StatePublished - Jun 1 2016


  • Common subexpressions
  • Distributed databases
  • Event and stream processing
  • Heuristic rules
  • LINQ
  • SQL
  • XQuery

ASJC Scopus subject areas

  • Software
  • Information Systems
  • Hardware and Architecture
  • Information Systems and Management


Dive into the research topics of 'Detecting common subexpressions for multiple query optimization over loosely-coupled heterogeneous data sources'. Together they form a unique fingerprint.

Cite this