We're sorry but this page doesn't work properly without JavaScript enabled. Please enable it to continue.
Feedback

A Dichotomy for Homomorphism_Closed Queries on Probalistic Graphs

00:00
subtitles
off
playback rate
1
subtitles
off
English (auto-generated)
playback rate
0.25
0.5
0.75
1
1.25
1.5
1.75
2
quality
576p
51
 Cite
 Share
 Related Material
 Download Purchase
No logo availableInternational Conference on Database Theory (ICDT)
 Amarilli, Antoine Ceylan, Ismail Ilkan

Formal Metadata

Title
A Dichotomy for Homomorphism_Closed Queries on Probalistic Graphs
Title of Series
Number of Parts
25
Author
License
CC Attribution 3.0 Germany:
You are free to use, adapt and copy, distribute and transmit the work or content in adapted or unchanged form for any legal purpose as long as the work is attributed to the author in the manner specified by the author or licensor.
Identifiers
Publisher
Release Date
Language

Content Metadata

Subject Area
Genre
Abstract
We study the problem of probabilistic query evaluation (PQE) over probabilistic graphs, namely, tuple-independent probabilistic databases (TIDs) on signatures of arity two. Our focus is the class of queries that is closed under homomorphisms, or equivalently, the infinite unions of conjunctive queries, denoted UCQ∞. Our main result states that all unbounded queries in UCQ∞ are #P-hard for PQE. As bounded queries in UCQ∞ are already classified by the dichotomy of Dalvi and Suciu [Dalvi and Suciu, 2012], our results and theirs imply a complete dichotomy on PQE for UCQ∞ queries over probabilistic graphs. This dichotomy covers in particular all fragments in UCQ∞ such as negation-free (disjunctive) Datalog, regular path queries, and a large class of ontology-mediated queries on arity-two signatures. Our result is shown by reducing from counting the valuations of positive partitioned 2-DNF formulae (#PP2DNF) for some queries, or from the source-to-target reliability problem in an undirected graph (#U-ST-CON) for other queries, depending on properties of minimal models.
00:00
DichotomyQuery languageHomomorphismusClosed setGraph (mathematics)Customer relationship managementUniverse (mathematics)State of matterDomain nameVertex (graph theory)Relational databaseGraph (mathematics)Endliche ModelltheorieRepresentation (politics)Table (information)DatabaseInterpreter (computing)Grass (card game)PurchasingComputer animation
00:48
Data modelGraph (mathematics)DatabaseIndependence (probability theory)SubsetTelecommunicationMögliche-Welten-SemantikRepresentation (politics)DatabaseEndliche ModelltheorieProbability distributionGraph (mathematics)ExistenceState of matterGraph theoryQuery languageSubsetMultiplication signWebsiteBoss CorporationOrbitIndependence (probability theory)Bit rateLevel (video gaming)StatisticsGrass (card game)Computer animation
01:52
Graph (mathematics)Query languagePattern languageHomomorphismusRegular graphInequality (mathematics)InfinityQuery languagePrime numberPattern languageHomomorphismusGraph (mathematics)outputMatching (graph theory)Vertex (graph theory)Element (mathematics)Category of beingFunctional (mathematics)Social classJunction (traffic)FinitismusLengthInequality (mathematics)Validity (statistics)Formal languageFormal grammarVariable (mathematics)Regular graphCASE <Informatik>Grass (card game)Closed setTask (computing)Physical systemCoalitionSelf-organizationInstance (computer science)Forcing (mathematics)Sign (mathematics)Equivalence relationOffice suiteWebsiteDatabaseComputer animation
03:39
Query languageInstance (computer science)Performance appraisalStatement (computer science)outputTelecommunicationFunction (mathematics)Total S.A.Kolmogorov complexityTask (computing)Query languageDistribution (mathematics)outputDatabaseInstance (computer science)Performance appraisalComplex (psychology)Mögliche-Welten-SemantikForm (programming)NeuroinformatikComputer animation
04:31
P (complexity)DichotomyQuery languageTheoremException handlingRecursionRelational databaseOntologySet (mathematics)Formal languageAtomic numberContext awarenessTask (computing)P (complexity)Performance appraisalQuery languageComputational complexity theorySocial classHomomorphismusDichotomyException handlingInstance (computer science)LogicContent (media)Physical lawInjektivitätWordBound stateVotingComputer animation
05:40
Personal digital assistantObservational studyHomomorphismusQuery languageEquivalence relationKolmogorov complexityComplex (psychology)DichotomySocial classMultiplication signFormal languageResultantQuery languageCASE <Informatik>InfinityGraph (mathematics)Homomorphismus1 (number)Closed setWordRegular graphPerformance appraisalOffice suiteExecution unitINTEGRALData conversionSelf-organizationDecision tree learningMereologyComputer configurationLevel (video gaming)Equivalence relationComputer animation
07:12
Proof theoryData structurePattern languageHomomorphismusQuery languageGraph (mathematics)NP-hardProof theoryQuery languageGraph (mathematics)Instance (computer science)Pattern languagePerformance appraisalMereologyEquivalence relationLatent heatHomomorphismusException handlingBound stateDichotomyEndliche ModelltheorieFreewareIdentical particlesComputer animation
08:19
Pattern languageGraph (mathematics)HomomorphismusQuery languageQuery languageNP-hardTransformation (genetics)Pattern languageGraph (mathematics)Endliche ModelltheoriePoint (geometry)Maxima and minimaComputer animation
08:52
Query languagePattern languageLatent heatInstance (computer science)Right angleLengthGraph (mathematics)Green's functionQuery languageNP-hardProof theoryMögliche-Welten-SemantikHomomorphismusPattern languageReduction of orderMatching (graph theory)Social classPerformance appraisalData structureBoss CorporationPhysical lawWebsiteElectronic mailing listCuboidOffice suiteComputer animation
11:03
Pattern languageProof theoryQuery languageCASE <Informatik>Pattern languageNP-hardNumberIterationQuery languageCASE <Informatik>Proof theoryGraph (mathematics)Multiplication signBit rateDegree (graph theory)Grass (card game)ChainSystem calloutputControl flowSoftware testingReduction of orderComputer animation
12:20
NP-hardPattern languageoutputGraph (mathematics)Directed graphFunction (mathematics)Connectivity (graph theory)Query languageConnectivity (graph theory)Pattern languageGraph (mathematics)Mögliche-Welten-SemantikoutputIdentical particlesVertex (graph theory)LengthProbability distributionQuery languageHomomorphismusRight angleResultantDirected graphFilm editingProof theoryReduction of orderBitData conversionAverageParameter (computer programming)AuthorizationComputational complexity theoryUniform resource locatorPrisoner's dilemmaComputer animation
13:50
Query languageHomomorphismusDichotomyPerformance appraisalComputational complexity theoryOpen setGraph theoryDatabaseTransformation (genetics)Instance (computer science)Transformation (genetics)CASE <Informatik>Performance appraisalHomomorphismusContext awarenessQuery languageComputational complexity theoryProof theoryInstance (computer science)Graph theoryNP-hardDichotomyResultantObservational studyGrass (card game)KnotPerturbation theoryWorkstation <Musikinstrument>Food energyDifferent (Kate Ryan album)Computer animation
Transcript: English(auto-generated)