On Two Kinds of Dataset Decomposition

Research output: Chapter in Book/Report/Conference proceedingConference contributionResearchpeer-review

3 Citations (Scopus)


We consider a Cartesian decomposition of datasets, i.e. finding datasets such that their unordered Cartesian product yields the source set, and some natural generalization of this decomposition. In terms of relational databases, this means reversing the SQL CROSS JOIN and INNER JOIN operators (the last is equipped with a test verifying the equality of a tables attribute to another tables attribute). First we outline a polytime algorithm for computing the Cartesian decomposition. Then we describe a polytime algorithm for computing a generalized decomposition based on the Cartesian decomposition. Some applications and relating problems are discussed.

Original languageEnglish
Title of host publicationComputational Science – ICCS 2018 - 18th International Conference, Proceedings
EditorsY Shi, H Fu, Y Tian, VV Krzhizhanovskaya, MH Lees, J Dongarra, PMA Sloot
PublisherSpringer-Verlag GmbH and Co. KG
Number of pages13
ISBN (Print)9783319937007
Publication statusPublished - 1 Jan 2018
Event18th International Conference on Computational Science, ICCS 2018 - Wuxi, China
Duration: 11 Jun 201813 Jun 2018

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume10861 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference18th International Conference on Computational Science, ICCS 2018


  • Compactification
  • Data analysis
  • Databases
  • Decision tables
  • Decomposition
  • Functional dependency
  • Knowledge discovery
  • Optimization of boolean functions


Dive into the research topics of 'On Two Kinds of Dataset Decomposition'. Together they form a unique fingerprint.

Cite this