Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Bücher
Zeitschriften
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
SLX-Digitalkonferenz: Zukunftswerkstatt 2024

Mehr Umsatz mit Top-Kontakten

Am 7. Mai erfahren Sie, wie Vertriebsteams Leadgenerierung, Leadnurturing und Leadstrategien effizient steuern können.
Erweiterte Suche
Anmelden
nach oben
Acta Informatica
Erschienen in: Acta Informatica 1/2018

18.10.2016 | Original Article

Conjunctive query containment over trees using schema information

verfasst von: Henrik Björklund, Wim Martens, Thomas Schwentick

Erschienen in: Acta Informatica | Ausgabe 1/2018

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

We study the containment, satisfiability, and validity problems for conjunctive queries over trees with respect to a schema. We show that conjunctive query containment and validity are 2EXPTIME -complete with respect to a schema, in both cases where the schema is given as a DTD or as a tree automaton. Furthermore, we show that satisfiability for conjunctive queries with respect to a schema can be decided in NP . The problem is NP -hard already for queries using only one kind of axis. Finally, we consider conjunctive queries that can test for equalities and inequalities of data values. Here, satisfiability and validity are decidable, but containment is undecidable, even without schema information. On the other hand, containment with respect to a schema becomes decidable again if the “larger” query is not allowed to use both equalities and inequalities.
Vorheriger Artikel Sparsification and subexponential approximation
Nächster Artikel Online edge coloring of paths and trees with a fixed number of colors

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Jetzt informieren
Fußnoten
1
We do not require CQs to be in prenex normal form. However, all formulas that we construct in the paper can be put in prenex normal form by simply renaming the variables and moving the quantifiers.
 
2
Notice that, as stated in the introduction, we assume that trees only take labels from a finite alphabet \(\varSigma \). Hence, for a conjunctive query Q, the set L(Q) also consists of trees over alphabet \(\varSigma \). In the rare cases where we consider trees without schema information, we state this explicitly.
 
3
Transforming an NTA to a reduced NTA can be done in polynomial time by first performing an emptiness test for every state of A, followed by a reachability test. Section 4.2 of [35] describes an algorithm for reducing a DTD. The algorithm for NTAs is analogous.
 
4
To the best of our knowledge, the full proof is unpublished. For the convenience of our readers, we provide Wood’s proof, which he kindly provided in a personal communication.
 
5
We assume \(\varDelta \) to contain all the data values we use in our proofs and examples.
 
6
This definition is done with the proof of Theorem 23 in the back of our minds and therefore more complicated than a reader might have expected. In this proof, the reader should think of \(x'\) and \(y'\) as being mapped to the same node.
 
7
Of course, the resulting equality atoms can be removed by suitable variable renaming.
 
8
For the purpose of the reduction, a node v of the query is a leaf node if and only if the query does not have any atom of the form \(\textit{Child}\,(v,w)\) or \(\textit{Child}\,^+(v,w)\).
 
9
We can assume w.l.o.g. that the free variables are the same in P and Q.
 
10
Here, structural constraints include node identities and VBCs allow comparison of data values to constants.
 
Literatur
1.
Abiteboul, S., Bourhis, P., Muscholl, A., Wu, Z.: Recursive queries on trees and data trees. In: International Conference on Database Theory (ICDT), pp. 93–104 (2013)
2.
Arenas, M., Barceló, P., Libkin, L., Murlak, F.: Foundations of Data Exchange. Cambridge University Press, Cambridge (2014)MATH
3.
4.
Benedikt, M., Bourhis, P., Senellart, P.: Monadic datalog containment. In: International Colloquium on Automata, Languages, and Programming (ICALP), pp. 79–91 (2012)
5.
6.
7.
Björklund, H., Martens, W., Schwentick, T.: Conjunctive query containment over trees. J. Comput. Syst. Sci. 77(3), 450–472 (2011)MathSciNetCrossRefMATH
8.
Björklund, H., Martens, W., Schwentick, T.: Validity of tree pattern queries with respect to schema information. In: Mathematical Foundations of Computer Science (MFCS), pp. 171–182 (2013)
9.
Bojanczyk, M., Kolodziejczyk, L.A., Murlak, F.: Solutions in XML data exchange. J. Comput. Syst. Sci. 79(6), 785–815 (2013)MathSciNetCrossRefMATH
10.
Bojanczyk, M., Murlak, F., Witkowski, A.: Containment of monadic datalog programs via bounded clique-width. In: International Colloquium on Automata, Languages, and Programming (ICALP), pp. 427–439 (2015)
11.
Bojanczyk, M., Muscholl, A., Schwentick, T., Segoufin, L.: Two-variable logic on data trees and XML reasoning. J. ACM 56(3), Art. no.13 (2009). doi:10.​1145/​1516512.​1516515
12.
13.
14.
Chandra, A.K., Merlin, P.M.: Optimal implementation of conjunctive queries in relational data bases. In: STOC, pp. 77–90 (1977)
15.
16.
17.
Czerwinski, W., David, C., Losemann, K., Martens, W.: Deciding definability by deterministic regular expressions. In: International Conference on Foundations of Software Science and Computation Structures (FOSSACS), pp 289–304. Springer, Berlin (2013)
18.
Czerwinski, W., Martens, W., Niewerth, M., Parys, P.: Minimization of tree pattern queries. In: Symposium on Principles of Database Systems (PODS), pp. 43–54 (2016)
19.
Czerwinski, W., Martens, W., Parys, P., Przybylko, M.: The (almost) complete guide to tree pattern containment. In: Symposium on Principles of Database Systems (PODS), pp. 117–130 (2015)
20.
David, C.: Complexity of data tree patterns over XML documents. In: MFCS, pp. 278–289 (2008)
21.
David, C., Gheerbrant, A., Libkin, L., Martens, W.: Containment of pattern-based queries over data trees. In: International Conference on Database Theory (ICDT), pp. 201–212 (2013)
22.
David, C., Hofman, P., Murlak, F., Pilipczuk, M.: Synthesizing transformations from XML schema mappings. In: International Conference on Database Theory (ICDT), pp. 61–71 (2014)
23.
David, C, Libkin, L., Murlak, F.: Certain answers for XML queries. In: Symposium on Principles of Database Systems (PODS), pp. 191–202 (2010)
24.
25.
26.
Geerts, F., Fan, W.: Satisfiability of XPath queries with sibling axes. In: DBPL, pp. 122–137 (2005)
27.
Gheerbrant, A., Libkin, L., Tan, T.: On the complexity of query answering over incomplete XML documents. In: ICDT, pp. 169–181 (2012)
28.
29.
Hidders, J.: Satisfiability of XPath expressions. In: DBPL, pp. 21–36 (2003)
30.
Kimelfeld, B., Sagiv, Y.: Revisiting redundancy and minimization in an XPath fragment. In: Extending Database Technology (EDBT), pp. 61–72 (2008)
31.
Kolaitis, P.G., Vardi, M.Y.: Conjunctive-query containment and constraint satisfaction. J. Comput. Syst. Sci. 61(2), 302–332 (2000)MathSciNetCrossRefMATH
32.
Lakshmanan, L.V.S., Ramesh, G., Wang, H., Zhao, Z.: On testing satisfiability of tree pattern queries. In: VLDB, pp. 120–131 (2004)
33.
34.
Martens, W., Neven, F.: On the complexity of typechecking top-down XML transformations. Theor. Comput. Sci. 336(1), 153–180 (2005)MathSciNetCrossRefMATH
35.
Martens, W., Neven, F., Schwentick, T.: Complexity of decision problems for XML schemas and chain regular expressions. SIAM J. Comput. 39(4), 1486–1530 (2009)MathSciNetCrossRefMATH
36.
Martens, W., Neven, F., Schwentick, T., Bex, G.J.: Expressiveness and complexity of XML schema. ACM Trans. Database Syst. 31(3), 770–813 (2006)CrossRef
37.
38.
39.
Murlak, F., Oginski, M., Przybylko, M.: Between tree patterns and conjunctive queries: Is there tractability beyond acyclicity? In: Mathematical Foundations of Computer Science (MFCS), pp. 705–717 (2012)
40.
Neven, F., Schwentick, T.: On the complexity of XPath containment in the presence of disjunction, DTDs, and variables. Log. Methods Comput. Sci. 2(3), Art. no. 1 (2006). doi:10.​2168/​LMCS-2(3:​1)2006
41.
42.
Räihä, K.J., Ukkonen, E.: The shortest common supersequence problem over binary alphabet is NP-complete. Theor. Comput. Sci. 16(2), 187–198 (1981)MathSciNetCrossRefMATH
43.
Takahashi, M.: Generalizations of regular sets and their application to a study of context-free languages. Inf. Control 27(1), 1–36 (1975)MathSciNetCrossRefMATH
44.
45.
Thatcher, James W., Wright, Jesse B.: Generalized finite automata theory with an application to a decision problem of second-order logic. Math. Syst. Theory 2(1), 57–81 (1968)MathSciNetCrossRefMATH
46.
Vardi, Moshe Y.: Reasoning about the past with two-way automata. In: Proceedings of the 25th International Colloquium on Automata, Languages and Programming (ICALP’98), Aalborg, Denmark, July 13–17, 1998, pp. 628–641 (1998)
47.
Wood, P.T.: Containment for XPath fragments under DTD constraints. In: ICDT, 2003. Full version, obtained through personal communication (2003)
Metadaten
Titel
Conjunctive query containment over trees using schema information
verfasst von
Henrik Björklund
Wim Martens
Thomas Schwentick
Publikationsdatum
18.10.2016
Verlag
Springer Berlin Heidelberg
Erschienen in
Acta Informatica / Ausgabe 1/2018
Print ISSN: 0001-5903
Elektronische ISSN: 1432-0525
DOI
https://doi.org/10.1007/s00236-016-0282-1