Containment of UC2RPQ: The Hard and Easy Cases
This is a modal window.
Das Video konnte nicht geladen werden, da entweder ein Server- oder Netzwerkfehler auftrat oder das Format nicht unterstützt wird.
Formale Metadaten
| Titel |
| |
| Serientitel | ||
| Anzahl der Teile | 25 | |
| Autor | ||
| Lizenz | CC-Namensnennung - keine Bearbeitung 3.0 Deutschland: Sie dürfen das Werk in unveränderter Form zu jedem legalen Zweck nutzen, vervielfältigen, verbreiten und öffentlich zugänglich machen, sofern Sie den Namen des Autors/Rechteinhabers in der von ihm festgelegten Weise nennen. | |
| Identifikatoren | 10.5446/46832 (DOI) | |
| Herausgeber | ||
| Erscheinungsjahr | ||
| Sprache |
Inhaltliche Metadaten
| Fachgebiet | ||
| Genre | ||
| Abstract |
|
2
00:00
Data Encryption StandardFinite-Elemente-MethodeRegulärer GraphVirtualisierungDatenbankMultigraphGraphAbfrageComputeranimation
00:18
RahmenproblemGraphFinitismusZeichenvorratDesign by ContractMaßerweiterungGebäude <Mathematik>Beobachtungsstudiep-BlockZellularer AutomatRegulärer GraphFormale SpracheComputeranimation
00:33
BildschirmmaskeRekursive FunktionMaßerweiterungGebäude <Mathematik>Graphp-BlockOrdinalzahlAbfrageComputeranimation
00:52
KnotenpunktRelativitätstheorieReguläre SpracheBildschirmmaskeComputeranimation
01:03
Regulärer GraphMultigraphReguläre SpracheSchnittmengeComputeranimation
01:13
ResultanteDivergente ReiheGraphVorzeichen <Mathematik>DatenbankComputeranimation
01:26
LeistungsbewertungGraphFormale SemantikAbfrageIRIS-TMultigraphGerichteter GraphComputeranimation
01:45
Elektronische PublikationGerichteter GraphBildschirmmaskeWort <Informatik>Folge <Mathematik>MultigraphFormale Sprache
02:03
Generator <Informatik>
02:26
Funktion <Mathematik>KnotenmengeSchnittmengeAbfrageTonnelierter RaumComputeranimation
02:55
ResultanteBeobachtungsstudieDatenbankGraphComputeranimation
03:23
Elektronische PublikationComputeranimation
03:38
SchlussregelFermatsche VermutungNP-hartes ProblemAbfrageVariableResultanteQuadratzahlComputeranimation
03:58
SchlussregelBoolesche AlgebraShape <Informatik>VollständigkeitSchnittmengeFormale SpracheAggregatzustandGraphfärbungComputeranimation
04:26
SchlussregelElektronische PublikationAbfrageSchnittmengeFormale SpracheXML
04:44
Elektronische PublikationZahlenbereichBildgebendes VerfahrenMultigraphAbfrageParallele SchnittstelleKategorie <Mathematik>Computeranimation
05:02
SchlussregelEinflussgrößeShape <Informatik>Klasse <Mathematik>EreignishorizontGRASS <Programm>AggregatzustandProgrammierungMinkowski-MetrikGraphfärbungPhysikalische TheorieBridge <Kommunikationstechnik>MagnettrommelspeicherEndliche ModelltheorieCliquenweiteVollständigkeitAbfrageTheoremComputeranimation
05:57
TheoremTopologieGraphProzess <Informatik>
06:17
Elektronische PublikationRahmenproblemBridge <Kommunikationstechnik>Luenberger-BeobachterVollständigkeit
06:34
Elektronische PublikationKlasse <Mathematik>EinflussgrößeMultigraphVollständigkeitCliquenweite
07:00
Bridge <Kommunikationstechnik>CliquenweiteEinflussgrößeElement <Gruppentheorie>Klasse <Mathematik>GraphWeb-SeiteGRASS <Programm>Computeranimation
07:32
Lie-GruppeMultigraphElektronische PublikationTopologieUmsetzung <Informatik>CliquenweiteBridge <Kommunikationstechnik>Klasse <Mathematik>StichprobenumfangCASE <Informatik>ErneuerungstheorieComputeranimation
08:08
SchlussregelHill-DifferentialgleichungGraphBridge <Kommunikationstechnik>Parallele SchnittstelleCliquenweite
08:20
SchlussregelZahlenbereichWhiteboardLokales MinimumGRASS <Programm>Bridge <Kommunikationstechnik>MultigraphCliquenweiteSchnittmengeGraphEinfach zusammenhängender RaumComputeranimation
08:43
Elektronische PublikationGradientGRASS <Programm>Shape <Informatik>ResultanteMultigraphMinkowski-MetrikKlasse <Mathematik>DichotomieComputeranimation
09:04
GradientElektronische PublikationSchlussregelMultigraphTopologieParallele SchnittstelleBridge <Kommunikationstechnik>InstantiierungZahlenbereichFamilie <Mathematik>CliquenweiteComputeranimation
09:18
SchlussregelPhysikalische TheorieInstantiierungResultanteAggregatzustandFolge <Mathematik>EinsMinkowski-MetrikInverseOrdnungsreduktionMultigraphBridge <Kommunikationstechnik>CliquenweiteHelmholtz-ZerlegungComputeranimation
10:07
Lokales MinimumIkosaederSchlussregelAbfrageTheoremInverseComputeranimation
10:35
SchlussregelE-FunktionTheoremComputeranimation
10:44
Elektronische PublikationGRASS <Programm>Prädiktor-Korrektor-VerfahrenProzess <Informatik>Formale SpracheKlasse <Mathematik>Web-SeiteTermRegulärer Ausdruck <Textverarbeitung>TabelleSchnittmengeShape <Informatik>Reguläre SpracheAbfrageComputeranimation
11:35
SchlussregelMachsches PrinzipWeb-SeiteRegulärer Ausdruck <Textverarbeitung>AbfrageBeobachtungsstudieMAPComputeranimation
12:10
VerschlingungComputeranimation
Transkript: Englisch(automatisch erzeugt)
00:01
Hello, and welcome to the virtual session on query containment. I'm Diego Figueira, and this is a work on containment for regular path queries on graph databases. Now for our purposes here, a graph database is just an edge labeled finite graph,
00:25
like this one, where A is a finite alphabet of labels. So the language we study is conjunctive regular path queries, or CRPQs. This is a basic building block for querying graph structured data,
00:41
and it is basically the extension of conjunctive queries with some simple form of recursion. CRPQs are just like conjunctive queries, where instead of having a conjunction of atoms over a binary relation, we have a conjunction of things of the form L1 to LN,
01:04
where L1 to LN are regular languages over the set of edge labels, which we usually write as arrows, like this. For example, this is a CRPQ, which can also be seen in a graph form, like this.
01:26
The semantics for the evaluation in a graph database, like this one, is such that a given assignment for the variables, like this one, satisfies this query
01:41
if for every edge of the query there exists a directed path from the node assigned to the source to the node assigned to the target, whose sequence of labels forms a word from the edge language. For example, this is a satisfying assignment,
02:02
because for this edge, one can find a directed path, which is this one here, whose labels are in this language, and for this edge, one can find this green directed path,
02:26
which goes all the way here, which is in this language. So it is a satisfying assignment. And this satisfying assignment witnesses that the pair of vertices B1, B2 here
02:46
are in the output of the query when evaluated on this graph, and we write it like this. It is a pair, because remember that the variable set is existentially quantified.
03:02
Okay. The containment problem, the problem we study here in this work, is the following. Given two CRPQs, Q1 and Q2, whether for every graph database G, every result of Q1 is also a result of Q2.
03:24
The containment problem for CRPQs is in general X-based complete, and this is nothing new. It's been known for more than 20 years now. And this hardness result holds even for queries of a very simple shape.
03:47
Like this one here, that is only two variables which are quantified, and the left query is just an atom.
04:01
Then this means that given this set of multigraphs P, basically all possible parallel edges, the fragment of CRPQs restricted to the shapes of P, which we call here CRPQP, is still X-based hard, X-based complete.
04:27
To be clear, by CRPQP, we mean the set of all queries whose underlying multigraph, so if we remove the languages and the arrows, it is in P.
04:48
Note that the important property here is that the number of parallel edges on the right-hand side query is unbounded. Otherwise, the problem would be in PSPACE.
05:02
The question we pose here is the following. Which shapes of queries ensure a PSPACE containment problem? More concretely, for a class of multigraph C, can we tell whether the containment problem is in PSPACE?
05:24
Can we tell whether it is X-based complete? Can it be complete for some in-between classes? And this is the question we answer, and the main theorem is this one. For every class of multigraphs, the containment problem is either PSPACE complete or X-based complete.
05:44
There is no middle point. And this depends on whether the bridge width of the class is bounded or unbounded. So now you may wonder, what is bridge width? It is a graph measure, just like tree width, but different,
06:06
that we introduce to this end, so that the theorem holds, basically. But it is a rather intuitive measure, you will see. Observe that we will need to have that P has unbounded bridge width,
06:25
since we said the containment problem for P is X-based complete. And note that, however, P has bounded tree width, so this measure will not quite be tree width.
06:43
In fact, it follows easily that every class containing infinitely many graphs from P has an X-based complete containment problem. And this is even true if it contains them as minors.
07:01
So, well, basically, this can be taken as the definition of unbounded bridge width. So a class has unbounded bridge width if and only if it contains infinitely many elements from P as minors.
07:20
And the concrete measure associated to this idea is that a graph has bridge width K if it contains this graph with K edges, but not this one with K plus one edges as a minor. So, for example, a tree then has bridge width one,
07:45
a large grid has large bridge width, and then any class of large tree width has large bridge width, but the converse is false. And, in fact, tree width is always smaller or equal to bridge width.
08:01
So something of tree width K has bridge width at least K. For example, here, this one has tree width two, but it has bridge width four, because it contains the four parallel edges graph as minor.
08:22
If you don't like my definition, I have others. Here is another equivalent definition. Define a bridge to be a minimal set of edges whose removal increases the number of connected components. Then the bridge width of a graph is the maximum size of its bridges.
08:45
And this dichotomy result between P space and X space had already been shown for the class of tree-like graphs. Actually, in the literature, they call it acyclic, but I find it confusing. So these are defined as graphs with this shape.
09:03
Basically, I will not go into detail, but that is trees with parallel edges and self-loops. And restricted to this class, a subclass has bounded bridge width if and only if there is a bound on the number of parallel edges.
09:21
So it's a particular instance of our theory. Our result can then be seen as a generalization of these results that appears in this paper to all graphs. And I will actually not talk about the P space upper bound
09:42
of the main theorem, which is the main technical contribution. You can read the paper. It's a long and tedious sequence of reductions which follows closely the ones of this paper here, with the additional insights of some decomposition lemmas
10:03
for bounded bridge width graphs. Now, I'd like to finish with two remarks. First, the upper bound holds even if we have arbitrary CRPQs in the left-hand query. And second, the same theorem holds
10:22
if we also allow inverse navigation in queries. I will not define it now because I don't have the time. And if we also have unions, this is known as UC2RPQ. So here, we can replace in the theorem CRPQs
10:42
by UC2RPQ or by anything in between, like C2RPQ or UCRPQ. And it will still hold. And finally, a piece of advertisement.
11:02
Contrary to conjunctive queries, defining fragments in terms of the shape of queries is not the only way to go. One could alternatively define for any class of regular languages the set of all CRPQs
11:22
which only use languages from the class. And we have studied also this possibility with a lot of co-authors, as you can see, in a yet-unpublished paper that you can find on our archive or on my web page
11:41
where the fragments of regular expressions are motivated by practically relevant queries as shown in some recent studies. So this is another take in studying the containment problems for CRPQs. And that is all.
12:02
I don't know if I'm already 12 minutes. I forgot. Okay. Thank you for listening or watching if you're still there.