A First Attempt to Computing Generic Set Partitions: Delegation to an SQL Query Engine

International audiencePartitions are a very common and useful way of organiz- ing data, in data engineering and data mining. However, partitions cur- rently lack efficient and generic data management functionalities. This paper proposes advances in the understanding of this problem, as well as elements for solving it. We formulate the task as efficient processing, evaluating and optimizing queries over set partitions, in the setting of re- lational databases. We first demonstrate that there is no trivial relational modeling for managing collections of partitions. We formally motivate a relational encoding and show that one cannot express all the operators of the partition lattice and set-theoretic operations as queries of the re- lational algebra. We provide multiple evidence of the inefficiency of FO queries. Our experimental results enforce this evidence. We claim that there is a strong requirement for the design of a dedicated system to manage set partitions, or at least to supplement an existing data man- agement system, to which both data persistence and query processing could be delegated