A Dichotomy for Homomorphism Closed Queries on Probalistic Graphs
Formal Metadata
Title 
A Dichotomy for Homomorphism Closed Queries on Probalistic Graphs

Title of Series  
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 
2020

Language 
English

Content Metadata
Subject Area  
Abstract 
We study the problem of probabilistic query evaluation (PQE) over probabilistic graphs, namely, tupleindependent 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 #Phard 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 negationfree (disjunctive) Datalog, regular path queries, and a large class of ontologymediated queries on aritytwo signatures. Our result is shown by reducing from counting the valuations of positive partitioned 2DNF formulae (#PP2DNF) for some queries, or from the sourcetotarget reliability problem in an undirected graph (#USTCON) for other queries, depending on properties of minimal models.

Related Material
00:00
Domain name
Purchasing
Closed set
Relational database
State of matter
Graph (mathematics)
Database
Grass (card game)
Dichotomy
Customer relationship management
Graph (mathematics)
Universe (mathematics)
Query language
Interpreter (computing)
Table (information)
Homomorphismus
00:48
Statistics
Graph (mathematics)
Multiplication sign
MöglicheWeltenSemantik
Database
Prime number
Inequality (mathematics)
Junction (traffic)
Subset
Formal language
Independence (probability theory)
Data model
Sign (mathematics)
Regular graph
Bit rate
Telecommunication
Query language
Pattern language
Endliche Modelltheorie
Office suite
Homomorphismus
Task (computing)
Physical system
Boss Corporation
Matching (graph theory)
Coalition
Closed set
Forcing (mathematics)
Independence (probability theory)
Infinity
Database
Instance (computer science)
Grass (card game)
Equivalence relation
Inequality (mathematics)
Orbit
Subset
Personal digital assistant
Website
Selforganization
03:39
Complex (psychology)
MöglicheWeltenSemantik
Dichotomy
Instance (computer science)
Total S.A.
Neuroinformatik
P (complexity)
Performance appraisal
Telecommunication
Query language
Statement (computer science)
output
Form (programming)
Exception handling
Social class
Injektivität
Distribution (mathematics)
Kolmogorov complexity
Physical law
Content (media)
Bound state
Database
Instance (computer science)
Word
Voting
Dichotomy
Logic
Function (mathematics)
Theorem
Exception handling
05:40
Decision tree learning
Complex (psychology)
Observational study
INTEGRAL
Kolmogorov complexity
Execution unit
1 (number)
Dichotomy
Mereology
Equivalence relation
Equivalence relation
Formal language
Word
Computer configuration
Personal digital assistant
Personal digital assistant
Query language
Selforganization
Data conversion
Office suite
Homomorphismus
Data structure
Resultant
Proof theory
07:15
Latent heat
Transformation (genetics)
Graph (mathematics)
Query language
Pattern language
Pattern language
Instance (computer science)
Endliche Modelltheorie
Freeware
Identical particles
Homomorphismus
08:52
Boss Corporation
Matching (graph theory)
Physical law
MöglicheWeltenSemantik
Electronic mailing list
Instance (computer science)
Latent heat
Green's function
Query language
Reduction of order
Pattern language
Cuboid
Website
Right angle
Pattern language
Office suite
Data structure
Proof theory
11:08
Multiplication sign
Control flow
Grass (card game)
System call
Number
Degree (graph theory)
Bit rate
Personal digital assistant
Personal digital assistant
Chain
Order (biology)
Query language
Reduction of order
Pattern language
output
Iteration
Pattern language
Software testing
Proof theory
12:20
Source code
NPhard
Graph (mathematics)
Prisoner's dilemma
Source code
MöglicheWeltenSemantik
Parameter (computer programming)
Computational complexity theory
Uniform resource locator
Film editing
Average
Function (mathematics)
Query language
Authorization
Reduction of order
Pattern language
Connectivity (graph theory)
Right angle
Data conversion
output
Resultant
13:50
Observational study
Workstation <Musikinstrument>
Database
Knot
Instance (computer science)
Perturbation theory
Instance (computer science)
Transformation (genetics)
Grass (card game)
Food energy
Open set
Computational complexity theory
Performance appraisal
Dichotomy
Personal digital assistant
Different (Kate Ryan album)
Graph (mathematics)
Query language
Homomorphismus
Resultant
00:00
a lover on and also another reason is that in paris and this is joined lloyds this knowledge can say in from university of oxford.
00:09
this is a talk about managing data which i will assume to be represented as enabled grass so if you're used to the interpretation of the data in is a relational database tables like this i instantly going to produce the domain of the data bases as purchases of the grass and drones starts as a as an edge in the. past labeled by the relations firm which i am assuming all relations and i urge you to which it will use roads. i am specific interest in resenting data on which is uncertain so we are not sure about what is the current state of the data the older they used to this is called struggle in the been in databases it is a very simple mall where we simply is soon to every act of the database every edge of the grass carries a probable.
00:58
yet exist as all the sites are since the independence every fact is present or out sons with a given probably seen advantage in the others what i call a possible worlds is a possible stage of the data so it is a subset of stats of the trouble in london database and every boss whole world has or will it see which. you can shoot using the orbits of the charity secured works and is your or your three percent a specific possible worlds get sorted edges and discarded the ashes and in general and problem with just a boss the world is completed like this so we can see a time when the monday today's as a. size of person dacia than exponentially sized collection as possible worlds and comfortable in kabul is this traditional so this is the model of them working with two thousand and seven data than in all talk about it all rating curries over such data but first let me find her his own novelistic grass so for me.
01:59
murray is always billion than simply assumption that sites including grass and richer and yes so some well known to encourage houses are concerned his worries that cost and i find a match up some better match here is a whole more systems of the out and the grass not inject. sulzer to turn to the same on grass. perhaps unions have confronted her wrist is awesome via destruction of or find it in many countries curries and if this were to study a more general clauses all more his i'm close to her so curries flows little under home organisms that it has the following are pretty given a grass it said the size of curry every grass to which the grass has a home. forces and must also set aside for so to get some intuition about this very general cross this is a closet generalize is using use use but also cover some other languages such as regular off or is a lot so what is not allowed in this film isn't would be inequalities between hurdles are. creation and another way to see all the more person whose careers is to see them as an infinite geniuses use so this junction of her infinity many seats humans and in this case will incur he founded it is a sign of genius of seats use so it is actually equivalence to use you another home office and close charisma. old and bounded not to see you. and of course is lost it also hurry weird were his last thing is there is an awesome the growth businesses prime number this is a birdie the incentives genius to use salt marshes and. so this is the korean language is that the the other will be studying at me not to look at all the task of where interested in on problems the data school troubles to create a coalition or you eat so for this which takes a career for instance this year and includes to this problem is in trouble in the database and one also.
03:59
the computer is to all probability of the world's all this database that satisfied with her wants to know intuitively what is the probability that the curry is true in the distribution represented by his charity so form of the were just consider all of the possible worlds and the song also than when they set aside of her visit. of course of her initial wage do things so we are interested more generally in figuring out what is the complexity of this problem you have used for the six courage you the bending of the murders you which.
04:32
this is something that has been studied already in previous work in particular the dichotomy by dolly in switching shows that for unions of content is curries saudis use all safe and enjoying article was encouraging and alter use use our and sage this unique cost is shocking heart. so in this dichotomy for instance you said you into it seems like this is safe but if i have a sore head and that it becomes and say. if are interested in more express his career is that has been some word based in an old said he would only asian that's to my knowledge there is no work and all trigger scurries so for instance the voting on tuesday the law. you only exception of them were all it's the word by human lives about apology it were answering this is a somewhat different tossed also sugaring out whether a hurry his logic implied i'd love to instance an apology and asia injectable itchy into trouble most exciting song which is of orange hue which employ. in the intractable its yost some classes for six or so in this work was done in this problem and into generalities for all the more has imposed worries and were able to show the following the will to me given a hurried closer to home or business either it is ignorance to say she's you name me it is bounded.
05:55
and these you tube which is equivalent stage or things don't in situ in this case the jury is in the town and in all other cases rose to her innovations sharkey heart so this generalize as a result of human the instant shoes or and converse languages such as r q a. you see two adults use data loggers her on its you want an example you could think of this regular us for he asked if there is an imposter redditch of new and she's in only green edges it is easy to see that this is not equivalent to use you because it is an instant it is charging us to choose the whole lot more to or less and so our results. and why is to do for was to her innovations for this for is shocking are actually the same goals or any options you except the ones that are not to be occurrence to say she's so natural question who needed in a hurry once the complexity of deciding which case of the dichotomy applies we do not study this because it would you bet on. our reserves and its we are studying these are large cross the home office and to currys which is only find some entity units and technically he would have to restrict its to his integrity defined frontman so this makes sense to me. so this is the results that we have shown and to use your words about how to prove this of course the difficult part is to show that even a hurry closer to home organisms it is unbounded than doubles to create real issues shopping cart this is deterred the difficult part because to bounded such worries they are in trouble.
07:30
since g.'s use and so they are classified already i did all the institute. so the idea of the truth is to find specific patterns of instances where the curry is true and he comes olds which we can use to do a harvest is currently did not know anything about all her except that it is close to home or is a well. so an interesting kind of pattern to use for honest truth is i'd better and this is what this is an instance that said the size of curry and hasn't cost free distinguished edges like this such that whenever we did the middle and and replace it by two edges disconnect the red and blue edge. then this fall a sticker or is no longer true in the instance. if we can find something like his bills are not useful should harness and we get actually sure that any career closer to home or dozens which is unbounded must have such the intuitions that and only hurries much how it must have been generating many minimal models so they must all be truly large minimal models and so we get so.
08:36
simply say as are large animal model and perform this transformation on the edges randomly and ordered there was no borders which to curry stubbs in true of the wide to contradict know it's just a lot smaller start. so we can show this and did a tighter and knowledge me explain to you how we can use this show heart.
08:58
the idea is to reduce for problems to curb politicians for this this is it and saves you use your own customs for office and three and we will study is jury problems for jews are on the specific laws of instances which his suspicions to show hardest by looking at all of the hardest a huge but use your his show. it's a crisis to consider instances where we haven't read adjust to the last are those you want haas you adjust to the right or who is one hot and green edges from the last the rights of herbal tea was given such an instance we concluded is as an instance for our problem simply by taking the. same structure and using the tide pattern creating copies of the red blue and green adjusts and the intuition is that also worlds of the left at how the boss matching she's euro will give us a possible worlds in the right where we have a match of the site or and sucker is true and has almost isn't. conversely if we say to the list of possible worlds where we do not have much as two zero and the possible world to get the right does not have a natural cider and so would like to argue that it does not set aside to worry so that the reduction is. it's hard for a salty here namely not only do we need to know that this connecting the green it will fall into a curry but we need more specifically to know that going back and forth on green edges blockade are rich or because issued a possible worlds that we have the right there is no box going from redditch should you wish. directed by their green but of course that could be bossed range from red to you by going back and forth all reneges so we will need to argue that these cannot suck the side of her is indeed these dollars to curry than the possible worlds to the right as a whole more season to this pattern that those lobsters. i do worry and sort of her is also wrong with the air so we cannot do the reductions. so we need to six to prove because all that we know is that we have a tight pattern that we do not know the status of this weird that and souls.
11:10
the.
11:12
so yeah deal is going to be studied just this is a pattern of going back and forth so this is the same better and just on a different way and to actually consider more iterations of this all the possible numbers times of could go back and forth on the edges the chain read it. i call this the its rates and now will distinguish two cases the first case is when there is some longer asked back and forth. iterations that will make a graceful so eventually going back and forth makes the crease holes in this case we could use the previous true that should you need to work the second case is when all of these iterate satisfied with her so going from read his job new as by the end. the number of back and forth on the green hatchlings richer but this connecting degree and just breaks for this could happen because we're looking at her is that could be rigors of greece testing for and all the arts or so in this case that school is an internal matter and let's show harness with a different reduction which reducing from of theirs. or so hard to use his actual data and social harness the idea is going to be reduced from the social order to connect to kabul on undirected so this is a sharp the heart problem where the input is an undirected gravest with a distinguished sorcerers acts as an auditor dickstein all edges of the grass have trouble.
12:39
the long haul and what he wants to compute is the probability that there is a lost from the source of the targets in the bubble is it is to do she represented by his. we can go in this using all the trouble better and by replacing every edge of the gravest by her back to a button souls bottles and two with green adjust it in problems you want hostile one of these urges all richer he and giving problem she wanted to read and do edges of the interval and then if we get abbas all worlds. of the interactive grassley the author ernest she then to the rights the corresponding also world will has not earned so your will or which some bottles of richard and win back and forth on the edges between red and blue edge which shows have the courage to converse lee possible worlds of the grasses last that does not have a boston. i still see it can be seen to be used also world's the rights that has a home or his and to the results of disconnecting the green and this can be shown following your cuts between us and she also world. so this is the basic idea of the reduction another going into the chiles a real culture. ok so to summarise we have shown that all secret location is intractable for encourage those little more prisons unless it is equivalent to say she's so this implies that they continue or all of their home or some posters and implies intractability for many career averages unless to occur his argument.
14:10
and swiss issues you so they're all the problems that remain one frustrating problem is that improves only applies to grass knots today today's auditor e r e g i would stay in the same result would work no matter the energy but when we need a somewhat different station issue of the instances of nations the u.n.. or the other question is is all abilities has to be won hasumi study and waited problems to croatia and do we still get heart so with an engine most all we recently showed that this was the case gone on here articles altering freesheet you so so there we already hot harness season when we were stuck in his own way to counter. and maybes these techniques also doubts or work for the reasons audience you not know how to artistic so that's all i had to say thanks also listening.