A formal characterization of PIVOT/UNPIVOT

ABSTRACT

PIVOT is an important relational operation that allows data in rows to be exchanged for columns. Although most current relational database management systems support PIVOT-type operations, to date a purely formal, algebraic characterization of PIVOT has been lacking. In this paper, we present a characterization in terms of extended relational algebra operators τ (transpose), Π (drop projection), and μ (unique optimal tuple merge). This enables us to (1) draw parallels with PIVOT and existing operators employed in Dynamic Data Mapping Systems (DDMS), (2) formally characterize invertible PIVOT instances, and (3) provide complexity results for PIVOT-type operations. These contributions are an important part of ongoing work on formal models for relational OLAP.

REFERENCES

• 1: Fulya Erdinc and Catharine M. Wyss. Intrinsic, Rule-Based Optimization of PIVOT and UNPIVOT Operations within RDBMS. Forthcoming.
• 2: Conor Cunningham, César A. Galindo-Legaria, and Goetz Graefe. PIVOT and UNPIVOT: Optimization and Execution Strategies in an RDBMS. VLDB 2004.
• 3: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• 4: Laks V. S. Lakshmanan , Fereidoon Sadri , Iyer N. Subramanian, SchemaSQL - A Language for Interoperability in Relational Multi-Database Systems, Proceedings of the 22th International Conference on Very Large Data Bases, p.239-250, September 03-06, 1996
• 5: Laks V. S. Lakshmanan , Fereidoon Sadri , Subbu N. Subramanian, SchemaSQL: An extension to SQL for multidatabase interoperability, ACM Transactions on Database Systems (TODS), v.26 n.4, p.476-519, December 2001 [doi>10.1145/503099.503102]
• 6: Raghu Ramakrishnan , Johannes Gehrke, Database Management Systems, McGraw-Hill, Inc., New York, NY, 1999
• 7: Edward L. Robertson and Catharine M. Wyss. Optimal Tuple Merge is NP-complete. IUCS Technical Report TR599, August 2004.
• 8: Catharine M. Wyss , Edward L. Robertson, Relational languages for metadata integration, ACM Transactions on Database Systems (TODS), v.30 n.2, p.624-660, June 2005 [doi>10.1145/1071610.1071618]
• 9: Andrew Witkowski , Srikanth Bellamkonda , Tolga Bozkaya , Gregory Dorman , Nathan Folkert , Abhinav Gupta , Lei Shen , Sankar Subramanian, Spreadsheets in RDBMS for OLAP, Proceedings of the 2003 ACM SIGMOD international conference on Management of data, June 09-12, 2003, San Diego, California [doi>10.1145/872757.872767]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Computations on discrete structures

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.1 Logical Design
          Subjects: Data models
      H.2.3 Languages
          Subjects: Query languages

General Terms:
Algorithms, Languages

Keywords:
FIRA, OLAP, PIVOT, UNPIVOT, data mapping, data modeling, exRA, extended RA, federated interoperable RA