On the expressive power of the relational algebra on finite sets of relation pairs

G.H.L. Fletcher, M. Gyssens, J. Paredaens, D. Van Gucht

Research output: Contribution to journalArticleAcademicpeer-review

15 Citations (Scopus)

Abstract

We give a language-independent characterization of the expressive power of the relational algebra on finite sets of source-target relation instance pairs. The associated decision problem is shown to be cograph-isomorphism hard and in coNP. The main result is also applied in providing a new characterization of the generic relational queries.
Original languageEnglish
Pages (from-to)939-942
JournalIEEE Transactions on Knowledge and Data Engineering
Volume21
Issue number6
DOIs
Publication statusPublished - 2009

Fingerprint

Dive into the research topics of 'On the expressive power of the relational algebra on finite sets of relation pairs'. Together they form a unique fingerprint.

Cite this