Campus Event Calendar: Nofar Carmeli (02/13/2020 in E1 4/024)

Campus Event Calendar

Campus Event Calendar:
- All Upcoming:
  - only for D1
  - only for D2
  - only for INET
  - only for D4
  - only for D5
  - only for D6
  - only for RG1
  - Mailing Lists
  - by Speaker
  - by Type
  - by Category
  - by Title
  - Calendar
  - RSS Feed
- History of Events:

Event Entry

What and Who

Enumeration Complexity of Unions of Conjunctive Queries

Nofar Carmeli

Technion

AG1 Mittagsseminar (own work)

AG 1, AG 5

AG Audience

English

Note: We use this to send email in the morning.

Date, Time and Location

Thursday, 13 February 2020

13:00

30 Minutes

E1 4

024

Saarbrücken

Abstract

We discuss the complexity of enumerating (listing) the answers to a query over a relational database. We focus on the ability to list the answers with linear preprocessing and constant time per answer. A known dichotomy classifies Conjunctive Queries (CQs) into those that admit such enumeration and those that do not. I will talk about our research towards extending this dichotomy to the class of Unions of CQs (UCQs). A union of tractable CQs is always tractable. We show that, counter to previous beliefs, some non-redundant unions containing intractable CQs are tractable. Interestingly, some unions consisting of only intractable CQs are tractable too. The question of finding a full characterization of the tractability of UCQs remains open.

Contact

Karl Bringmann

--email hidden

System used:

Meeting URL:

Meeting ID:

Passcode:

passcode not visible

Code Visible for:

logged in users only

Karl Bringmann, 01/21/2020 17:56 -- Created document.

Imprint / Impressum | Data Protection / Datenschutzhinweis