<?xml version="1.0" encoding="UTF-8"?>
<TEI xml:space="preserve" xmlns="http://www.tei-c.org/ns/1.0" 
xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" 
xsi:schemaLocation="http://www.tei-c.org/ns/1.0 https://raw.githubusercontent.com/kermitt2/grobid/master/grobid-home/schemas/xsd/Grobid.xsd"
 xmlns:xlink="http://www.w3.org/1999/xlink">
	<teiHeader xml:lang="en">
		<fileDesc>
			<titleStmt>
				<title level="a" type="main">The Query Containment Problem: Set Semantics vs. Bag Semantics</title>
			</titleStmt>
			<publicationStmt>
				<publisher/>
				<availability status="unknown"><licence/></availability>
			</publicationStmt>
			<sourceDesc>
				<biblStruct>
					<analytic>
						<author>
							<persName><forename type="first">Phokion</forename><forename type="middle">G</forename><surname>Kolaitis</surname></persName>
							<affiliation key="aff0">
								<orgName type="institution" key="instit1">UC Santa Cruz</orgName>
								<orgName type="institution" key="instit2">IBM Research -Almaden</orgName>
							</affiliation>
						</author>
						<title level="a" type="main">The Query Containment Problem: Set Semantics vs. Bag Semantics</title>
					</analytic>
					<monogr>
						<imprint>
							<date/>
						</imprint>
					</monogr>
					<idno type="MD5">545ECEDA48938B6EA626CA48BC55651C</idno>
				</biblStruct>
			</sourceDesc>
		</fileDesc>
		<encodingDesc>
			<appInfo>
				<application version="0.7.2" ident="GROBID" when="2023-03-24T03:41+0000">
					<desc>GROBID - A machine learning software for extracting information from scholarly documents</desc>
					<ref target="https://github.com/kermitt2/grobid"/>
				</application>
			</appInfo>
		</encodingDesc>
		<profileDesc>
			<abstract>
<div xmlns="http://www.tei-c.org/ns/1.0"><p>Query containment is a fundamental algorithmic task in database query processing and optimization. Under set semantics, the query-containment problem for conjunctive queries has long been known to be NP-complete. SQL queries, however, are typically evaluated under bag semantics and return multisets as answers, since duplicates are not eliminated unless explicitly specified. The exact complexity of the query-containment problem for conjunctive queries under bag semantics has been an outstanding and rather poorly understood open problem for twenty years. In fact, to this date, it is not even known whether conjunctive-query containment under bag semantics is decidable. The goal of this talk is to draw attention to this fascinating problem by presenting a comprehensive overview of old and not-so-old results about the complexity of the query-containment problem for conjunctive queries and their variants, under both set semantics and bag semantics.</p></div>
			</abstract>
		</profileDesc>
	</teiHeader>
	<text xml:lang="en">
		<body/>
		<back>
			<div type="references">

				<listBibl/>
			</div>
		</back>
	</text>
</TEI>
