Skip to main content

2016 | OriginalPaper | Buchkapitel

Hilbert-Style Axiomatization for Hybrid XPath with Data

verfasst von : Carlos Areces, Raul Fervari

Erschienen in: Logics in Artificial Intelligence

Verlag: Springer International Publishing

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

search-config
loading …

Abstract

In this paper we introduce a sound and complete axiomatization for XPath with data constraints extended with hybrid operators. First, we define \(\text {HXPath} _=({{\uparrow }{\downarrow }})\), an extension of vertical XPath with nominals and the hybrid operator @. Then, we introduce an axiomatic system for \(\text {HXPath} _=({{\uparrow }{\downarrow }})\), and we prove it is complete with respect to the class of abstract data trees, i.e., data trees in which data values are abstracted as equivalence relations. As a corollary, we also obtain completeness with respect to the class of concrete data trees.

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!

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!

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!

Literatur
1.
Zurück zum Zitat Abriola, S., Descotte, M., Fervari, R., Figueira, S.: Axiomatizations for downward XPath on data trees. CoRR, abs/1605.04271 (2016) Abriola, S., Descotte, M., Fervari, R., Figueira, S.: Axiomatizations for downward XPath on data trees. CoRR, abs/1605.04271 (2016)
3.
Zurück zum Zitat Abriola, S., Descotte, M.E., Figueira, S.: Definability for downward and vertical XPath on data trees. In: Kohlenbach, U., Barceló, P., Queiroz, R. (eds.) WoLLIC 2014. LNCS, vol. 8652, pp. 20–35. Springer, Heidelberg (2014). doi:10.1007/978-3-662-44145-9_2 Abriola, S., Descotte, M.E., Figueira, S.: Definability for downward and vertical XPath on data trees. In: Kohlenbach, U., Barceló, P., Queiroz, R. (eds.) WoLLIC 2014. LNCS, vol. 8652, pp. 20–35. Springer, Heidelberg (2014). doi:10.​1007/​978-3-662-44145-9_​2
4.
Zurück zum Zitat Areces, C., ten Cate, B.: Hybrid logics. In: Blackburn, P., Wolter, F., van Benthem, J. (eds.) Handbook of Modal Logics, pp. 821–868. Elsevier, Amsterdam (2006) Areces, C., ten Cate, B.: Hybrid logics. In: Blackburn, P., Wolter, F., van Benthem, J. (eds.) Handbook of Modal Logics, pp. 821–868. Elsevier, Amsterdam (2006)
5.
Zurück zum Zitat Baelde, D., Lunel, S., Schmitz, S.: A sequent calculus for a modal logic on finite data trees. In: 25th EACSL Annual Conference on Computer Science Logic, CSL 2016, pp. 32:1–32:16 (2016) Baelde, D., Lunel, S., Schmitz, S.: A sequent calculus for a modal logic on finite data trees. In: 25th EACSL Annual Conference on Computer Science Logic, CSL 2016, pp. 32:1–32:16 (2016)
7.
Zurück zum Zitat Benedikt, M., Koch, C.: XPath leashed. ACM Comput. Surv. 41(1), 1–54 (2008)CrossRef Benedikt, M., Koch, C.: XPath leashed. ACM Comput. Surv. 41(1), 1–54 (2008)CrossRef
8.
Zurück zum Zitat Blackburn, P., de Rijke, M., Venema, Y.: Modal Logic. Cambridge Tracts in Theoretical Computer Science, vol. 53. Cambridge University Press, Cambridge (2001)CrossRefMATH Blackburn, P., de Rijke, M., Venema, Y.: Modal Logic. Cambridge Tracts in Theoretical Computer Science, vol. 53. Cambridge University Press, Cambridge (2001)CrossRefMATH
9.
10.
Zurück zum Zitat Blackburn, P., van Benthem, J.: Modal logic: a semantic perspective. In: van Benthem, J., Blackburn, P., Wolter, F. (eds.) Handbook of Modal Logic, pp. 1–84. Elsevier, Amsterdam (2006) Blackburn, P., van Benthem, J.: Modal logic: a semantic perspective. In: van Benthem, J., Blackburn, P., Wolter, F. (eds.) Handbook of Modal Logic, pp. 1–84. Elsevier, Amsterdam (2006)
11.
Zurück zum Zitat Bojańczyk, M., Muscholl, A., Schwentick, T., Segoufin, L.: Two-variable logic on data trees and XML reasoning. J. ACM 56(3), 1–48 (2009)MathSciNetCrossRefMATH Bojańczyk, M., Muscholl, A., Schwentick, T., Segoufin, L.: Two-variable logic on data trees and XML reasoning. J. ACM 56(3), 1–48 (2009)MathSciNetCrossRefMATH
12.
15.
Zurück zum Zitat Figueira, D.: Reasoning on words and trees with data. Ph.D. thesis, Laboratoire Spécification et Vérification, ENS Cachan, France (2010) Figueira, D.: Reasoning on words and trees with data. Ph.D. thesis, Laboratoire Spécification et Vérification, ENS Cachan, France (2010)
17.
Zurück zum Zitat Figueira, D., Figueira, S., Areces, C.: Basic model theory of XPath on data trees. In: International Conference on Database Theory, pp. 50–60 (2014) Figueira, D., Figueira, S., Areces, C.: Basic model theory of XPath on data trees. In: International Conference on Database Theory, pp. 50–60 (2014)
18.
Zurück zum Zitat Figueira, D., Figueira, S., Areces, C.: Model theory of XPath on data trees. Part I: Bisimulation and characterization. J. Artif. Intell. Res. 53, 271–314 (2015)MathSciNetMATH Figueira, D., Figueira, S., Areces, C.: Model theory of XPath on data trees. Part I: Bisimulation and characterization. J. Artif. Intell. Res. 53, 271–314 (2015)MathSciNetMATH
19.
Zurück zum Zitat Figueira, D., Segoufin, L.: Bottom-up automata on data trees and vertical XPath. In: 28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011), pp. 93–104 (2011) Figueira, D., Segoufin, L.: Bottom-up automata on data trees and vertical XPath. In: 28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011), pp. 93–104 (2011)
20.
Zurück zum Zitat Gottlob, G., Koch, C., Pichler, R.: Efficient algorithms for processing XPath queries. ACM Trans. Database Syst. 30(2), 444–491 (2005)MathSciNetCrossRef Gottlob, G., Koch, C., Pichler, R.: Efficient algorithms for processing XPath queries. ACM Trans. Database Syst. 30(2), 444–491 (2005)MathSciNetCrossRef
21.
Zurück zum Zitat Kostylev, E., Reutter, J., Vrgoč, D.: Xpath for DL ontologies. In: Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence, AAAI 2015, pp. 1525–1531. AAAI Press (2015) Kostylev, E., Reutter, J., Vrgoč, D.: Xpath for DL ontologies. In: Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence, AAAI 2015, pp. 1525–1531. AAAI Press (2015)
22.
Zurück zum Zitat Marx, M.: XPath with conditional axis relations. In: Bertino, E., Christodoulakis, S., Plexousakis, D., Christophides, V., Koubarakis, M., Böhm, K., Ferrari, E. (eds.) EDBT 2004. LNCS, vol. 2992, pp. 477–494. Springer, Heidelberg (2004). doi:10.1007/978-3-540-24741-8_28 CrossRef Marx, M.: XPath with conditional axis relations. In: Bertino, E., Christodoulakis, S., Plexousakis, D., Christophides, V., Koubarakis, M., Böhm, K., Ferrari, E. (eds.) EDBT 2004. LNCS, vol. 2992, pp. 477–494. Springer, Heidelberg (2004). doi:10.​1007/​978-3-540-24741-8_​28 CrossRef
23.
Zurück zum Zitat Marx, M., de Rijke, M.: Semantic characterizations of navigational XPath. ACM SIGMOD Rec. 34(2), 41–46 (2005)CrossRef Marx, M., de Rijke, M.: Semantic characterizations of navigational XPath. ACM SIGMOD Rec. 34(2), 41–46 (2005)CrossRef
24.
Zurück zum Zitat Sattler, U., Vardi, M.Y.: The hybrid \({\mu }\)-calculus. In: Goré, R., Leitsch, A., Nipkow, T. (eds.) IJCAR 2001. LNCS, vol. 2083, pp. 76–91. Springer, Heidelberg (2001). doi:10.1007/3-540-45744-5_7 CrossRef Sattler, U., Vardi, M.Y.: The hybrid \({\mu }\)-calculus. In: Goré, R., Leitsch, A., Nipkow, T. (eds.) IJCAR 2001. LNCS, vol. 2083, pp. 76–91. Springer, Heidelberg (2001). doi:10.​1007/​3-540-45744-5_​7 CrossRef
Metadaten
Titel
Hilbert-Style Axiomatization for Hybrid XPath with Data
verfasst von
Carlos Areces
Raul Fervari
Copyright-Jahr
2016
DOI
https://doi.org/10.1007/978-3-319-48758-8_3

Premium Partner