Navegar

Colección

Datos Estadísticas

Artículo

Abriola, S.; Descotte, M.E.; Fervari, R.; Figueira, S. "Axiomatizations for downward XPath on data trees" (2017) Journal of Computer and System Sciences. 89:209-245
Estamos trabajando para incorporar este artículo al repositorio
Consulte el artículo en la página del editor
Consulte la política de Acceso Abierto del editor

Abstract:

We give sound and complete axiomatizations for XPath with data tests by ‘equality’ or ‘inequality’, and containing the single ‘child’ axis. This data-aware logic predicts over data trees, which are tree-like structures whose every node contains a label from a finite alphabet and a data value from an infinite domain. The language allows us to compare data values of two nodes but cannot access the data values themselves (i.e. there is no comparison by constants). Our axioms are in the style of equational logic, extending the axiomatization of data-oblivious XPath, by B. ten Cate, T. Litak and M. Marx. We axiomatize the full logic with tests by ‘equality’ and ‘inequality’, and also a simpler fragment with ‘equality’ tests only. Our axiomatizations apply both to node expressions and path expressions. The proof of completeness relies on a novel normal form theorem for XPath with data tests. © 2017 Elsevier Inc.

Registro:

Documento: Artículo
Título:Axiomatizations for downward XPath on data trees
Autor:Abriola, S.; Descotte, M.E.; Fervari, R.; Figueira, S.
Filiación:Departamento de Computación, FCEN, Universidad de Buenos Aires, ICC-CONICET, Argentina
Departamento de Computación, FCEN, Universidad de Buenos Aires, IMAS-CONICET, Argentina
FAMAF, Universidad Nacional de Córdoba, CONICET, Argentina
Palabras clave:Axiomatization; Data tree; Modal logic; Normal form; Query language; XML; XPath; Computer circuits; Query languages; XML; Axiomatization; Data tree; Modal logic; Normal form; XPath; Trees (mathematics)
Año:2017
Volumen:89
Página de inicio:209
Página de fin:245
DOI: http://dx.doi.org/10.1016/j.jcss.2017.05.008
Título revista:Journal of Computer and System Sciences
Título revista abreviado:J. Comput. Syst. Sci.
ISSN:00220000
CODEN:JCSSB
Registro:https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_00220000_v89_n_p209_Abriola

Referencias:

  • Abriola, S., Barceló, P., Figueira, D., Figueira, S., Bisimulations on data graphs (2016) Principles of Knowledge Representation and Reasoning: Proceedings of the Fifteenth International Conference, KR, pp. 309-318
  • Abriola, S., Descotte, M.E., Figueira, S., Model theory of XPath on data trees. Part II: binary bisimulation and definability (2017) Inf. Comput.
  • Abriola, S., Descotte, M.E., Figueira, S., Definability for downward and vertical XPath on data trees (2014) 21th Workshop on Logic, Language, Information and Computation, Lecture Notes in Computer Science, 6642, pp. 20-34
  • Artëmov, S.N., Krupski, V., Data storage interpretation of labeled modal logic (1996) Ann. Pure Appl. Log., 78 (1-3), pp. 57-71
  • Baelde, D., Lunel, S., Schmitz, S., A sequent calculus for a modal logic on finite data trees (2016) 25th EACSL Annual Conference on Computer Science Logic, CSL 2016, August 29–September 1, 2016, Marseille, France, pp. 321-32:16
  • Baier, C., Katoen, J., Principles of Model Checking (2008), MIT Press; Benedikt, M., Fan, W., Kuper, G.M., Structural properties of XPath fragments (2005) Theor. Comput. Sci., 336 (1), pp. 3-31
  • Bojańczyk, M., Muscholl, A., Schwentick, T., Segoufin, L., Two-variable logic on data trees and XML reasoning (2009) J. ACM, 56 (3), pp. 1-48
  • Cardelli, L., Ghelli, G., TQL: a query language for semistructured data based on the ambient logic (2004) Math. Struct. Comput. Sci., 14 (3), pp. 285-327
  • Clark, J., DeRose, S., XML path language (XPath) (1999), http://www.w3.org/TR/xpath, Website, W3C Recommendation; Figueira, D., Decidability of downward XPath (2012) ACM Trans. Comput. Log., 13 (4), p. 34
  • Figueira, D., Figueira, S., Areces, C., Basic model theory of XPath on data trees (2014) International Conference on Database Theory, pp. 50-60
  • Figueira, D., Figueira, S., Areces, C., Model theory of XPath on data trees. Part I: bisimulation and characterization (2015) J. Artif. Intell. Res., 53, pp. 271-314
  • Fine, K., Normal forms in modal logic (1975) Notre Dame J. Form. Log., 16 (2), pp. 229-237
  • Geerts, F., Fan, W., Satisfiability of XPath queries with sibling axes (2005) Database Programming Languages, 10th International Symposium, DBPL 2005, Trondheim, Norway, August 28–29, 2005, pp. 122-137. , Revised selected papers
  • Gottlob, G., Koch, C., Pichler, R., Efficient algorithms for processing XPath queries (2005) ACM Trans. Database Syst., 30 (2), pp. 444-491
  • Harel, D., Kozen, D., Tiuryn, J., Dynamic Logic (2000), MIT Press Cambridge, MA; Huntington, E.V., Boolean algebra. A correction to: “New sets of independent postulates for the algebra of logic, with special reference to Whitehead and Russell's Principia mathematica” [Trans. Amer. Math. Soc. 35 (1933), no. 1, 274–304; 1501684] (1933) Trans. Am. Math. Soc., 35 (2), pp. 557-558
  • Huntington, E.V., New sets of independent postulates for the algebra of logic, with special reference to Whitehead and Russell's Principia Mathematica (1933) Trans. Am. Math. Soc., 35 (1), pp. 274-304
  • Libkin, L., Vrgoč, D., Regular path queries on graphs with data (2012) International Conference on Database Theory, pp. 74-85
  • ten Cate, B., Fontaine, G., Litak, T., Some modal aspects of XPath (2010) J. Appl. Non-Class. Log., 20 (3), pp. 139-171
  • ten Cate, B., Litak, T., Marx, M., Complete axiomatizations for XPath fragments (2010) J. Appl. Log., 8 (2), pp. 153-172
  • ten Cate, B., Marx, M., Axiomatizing the logical core of XPath 2.0 (2009) Theory Comput. Syst., 44 (4), pp. 561-589

Citas:

---------- APA ----------
Abriola, S., Descotte, M.E., Fervari, R. & Figueira, S. (2017) . Axiomatizations for downward XPath on data trees. Journal of Computer and System Sciences, 89, 209-245.
http://dx.doi.org/10.1016/j.jcss.2017.05.008
---------- CHICAGO ----------
Abriola, S., Descotte, M.E., Fervari, R., Figueira, S. "Axiomatizations for downward XPath on data trees" . Journal of Computer and System Sciences 89 (2017) : 209-245.
http://dx.doi.org/10.1016/j.jcss.2017.05.008
---------- MLA ----------
Abriola, S., Descotte, M.E., Fervari, R., Figueira, S. "Axiomatizations for downward XPath on data trees" . Journal of Computer and System Sciences, vol. 89, 2017, pp. 209-245.
http://dx.doi.org/10.1016/j.jcss.2017.05.008
---------- VANCOUVER ----------
Abriola, S., Descotte, M.E., Fervari, R., Figueira, S. Axiomatizations for downward XPath on data trees. J. Comput. Syst. Sci. 2017;89:209-245.
http://dx.doi.org/10.1016/j.jcss.2017.05.008