Document Open Access Logo

Verification of Evolving Graph-structured Data under Expressive Path Constraints

Authors Diego Calvanese, Magdalena Ortiz, Mantas Šimkus

PDF
Thumbnail PDF

File

LIPIcs.ICDT.2016.15.pdf
  • Filesize: 1.64 MB
  • 19 pages

Document Identifiers

Author Details

Diego Calvanese
Magdalena Ortiz
Mantas Šimkus

Cite As Get BibTex

Diego Calvanese, Magdalena Ortiz, and Mantas Šimkus. Verification of Evolving Graph-structured Data under Expressive Path Constraints. In 19th International Conference on Database Theory (ICDT 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 48, pp. 15:1-15:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016) https://doi.org/10.4230/LIPIcs.ICDT.2016.15

Abstract

Integrity constraints play a central role in databases and, among other applications, are fundamental for preserving data integrity when databases evolve as a result of operations manipulating the data. In this context, an important task is that of static verification, which consists in deciding whether a given set of constraints is preserved after the execution of a given sequence of operations, for every possible database satisfying the initial constraints. In this paper, we consider constraints over graph-structured data formulated in an expressive Description Logic (DL) that allows for regular expressions over binary relations and their inverses, generalizing many of the well-known path constraint languages proposed for semi-structured data in the last two decades. In this setting, we study the problem of static verification, for operations expressed in a simple yet flexible language built from additions and deletions of complex DL expressions. We establish undecidability of the general setting, and identify suitable restricted fragments for which we obtain tight complexity results, building on techniques developed in our previous work for simpler DLs. As a by-product, we obtain new (un)decidability results for the implication problem of path constraints, and improve previous upper bounds on the complexity of the problem.

Subject Classification

Keywords
  • Path constraints
  • Description Logics
  • Graph databases
  • Static verification

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Serge Abiteboul, Richard Hull, and Victor Vianu. Foundations of Databases. Addison Wesley Publ. Co., 1995. Google Scholar
  2. Serge Abiteboul, Dallan Quass, Jason McHugh, Jennifer Widom, and Janet L. Wiener. The Lorel query language for semistructured data. Int. J. on Digital Libraries, 1(1):68-88, 1997. Google Scholar
  3. Serge Abiteboul and Victor Vianu. Regular path queries with constraints. J. of Computer and System Sciences, 58(3):428-452, 1999. Google Scholar
  4. Shqiponja Ahmetaj, Diego Calvanese, Magdalena Ortiz, and Mantas Šimkus. Managing change in Graph-structured Data using Description Logics. In Proc. of the 28th AAAI Conf. on Artificial Intelligence (AAAI), pages 966-973. AAAI Press, 2014. Google Scholar
  5. Renzo Angles and Claudio Gutierrez. Survey of graph database models. ACM Computing Surveys, 40(1):1:1-1:39, 2008. URL: http://dx.doi.org/10.1145/1322432.1322433.
  6. Marcelo Arenas, Wenfei Fan, and Leonid Libkin. On the complexity of verifying consistency of XML specifications. SIAM J. on Computing, 38(3):841-880, 2008. URL: http://dx.doi.org/10.1137/050646895.
  7. Alessandro Artale, Diego Calvanese, Roman Kontchakov, Vladislav Ryzhikov, and Michael Zakharyaschev. Reasoning over extended ER models. In Proc. of the 26th Int. Conf. on Conceptual Modeling (ER), volume 4801 of Lecture Notes in Computer Science, pages 277-292. Springer, 2007. Google Scholar
  8. Franz Baader, Diego Calvanese, Deborah L. McGuinness, Daniele Nardi, and Peter F. Patel-Schneider, editors. The Description Logic Handbook: Theory, Implementation and Applications. Cambridge University Press, 2003. Google Scholar
  9. Jie Bao et al. OWL 2 Web Ontology Language document overview (second edition). W3C Recommendation, World Wide Web Consortium, December 2012. URL: http://www.w3.org/TR/owl2-overview/.
  10. Daniela Berardi, Diego Calvanese, and Giuseppe De Giacomo. Reasoning on UML class diagrams. Artificial Intelligence, 168(1-2):70-118, 2005. Google Scholar
  11. Meghyn Bienvenu and Magdalena Ortiz. Ontology-mediated query answering with data-tractable description logics. In Reasoning Web. Web Logic Rules - 11th Int. Summer School Tutorial Lectures (RW), volume 9203 of Lecture Notes in Computer Science, pages 218-307. Springer, 2015. URL: http://dx.doi.org/10.1007/978-3-319-21768-0_9.
  12. Egon Börger, Erich Grädel, and Yuri Gurevich. The Classical Decision Problem. Perspectives in Mathematical Logic. Springer, 1997. Google Scholar
  13. Peter Buneman. Semistructured data. In Proc. of the 16th ACM SIGACT SIGMOD SIGART Symp. on Principles of Database Systems (PODS), pages 117-121, 1997. Google Scholar
  14. Peter Buneman, Wenfei Fan, and Scott Weinstein. Path constraints in semistructured databases. J. of Computer and System Sciences, 61(2):146-193, 2000. URL: http://dx.doi.org/10.1006/jcss.2000.1710.
  15. Diego Calvanese, Giuseppe De Giacomo, and Maurizio Lenzerini. Conjunctive query containment and answering under description logics constraints. ACM Trans. on Computational Logic, 9(3):22.1-22.31, 2008. Google Scholar
  16. Diego Calvanese, Giuseppe De Giacomo, Maurizio Lenzerini, and Moshe Y. Vardi. Reasoning on regular path queries. SIGMOD Record, 32(4):83-92, 2003. Google Scholar
  17. Diego Calvanese, Giuseppe De Giacomo, Maurizio Lenzerini, and Moshe Y. Vardi. View-based query processing: On the relationship between rewriting, answering and losslessness. Theoretical Computer Science, 371(3):169-182, 2007. Google Scholar
  18. Diego Calvanese, Thomas Eiter, and Magdalena Ortiz. Regular path queries in expressive description logics with nominals. In Proc. of the 21st Int. Joint Conf. on Artificial Intelligence (IJCAI), pages 714-720, 2009. Google Scholar
  19. Diego Calvanese, Evgeny Kharlamov, Werner Nutt, and Dmitriy Zheleznyakov. Evolution of DL-Lite knowledge bases. In Proc. of the 9th Int. Semantic Web Conf. (ISWC), volume 6496 of Lecture Notes in Computer Science, pages 112-128. Springer, 2010. Google Scholar
  20. Diego Calvanese, Magdalena Ortiz, and Mantas Šimkus. Containment of regular path queries under description logic constraints. In Proc. of the 22nd Int. Joint Conf. on Artificial Intelligence (IJCAI), pages 805-812, 2011. Google Scholar
  21. Giuseppe De Giacomo. Decidability of Class-Based Knowledge Representation Formalisms. PhD thesis, Dipartimento di Informatica e Sistemistica, Università di Roma "La Sapienza", 1995. Google Scholar
  22. Alin Deutsch and Val Tannen. Optimization properties for classes of conjunctive regular path queries. In Proc. of the 8th Int. Workshop on Database Programming Languages (DBPL), volume 2397 of Lecture Notes in Computer Science, pages 21-39. Springer, 2001. Google Scholar
  23. Wenfei Fan and Leonid Libkin. On XML integrity constraints in the presence of DTDs. J. of the ACM, 49(3):368-406, 2002. Google Scholar
  24. Michael J. Fischer and Richard E. Ladner. Propositional dynamic logic of regular programs. J. of Computer and System Sciences, 18:194-211, 1979. Google Scholar
  25. Erich Grädel and Martin Otto. On logics with two variables. Theoretical Computer Science, 224:73-113, 1999. Google Scholar
  26. Gösta Grahne and Alex Thomo. Query containment and rewriting using views for regular path queries under constraints. In Proc. of the 22nd ACM SIGACT SIGMOD SIGART Symp. on Principles of Database Systems (PODS), pages 111-122, 2003. Google Scholar
  27. Egor V. Kostylev, Juan L. Reutter, and Domagoj Vrgoc. Containment of data graph queries. In Proc. of the 17th Int. Conf. on Database Theory (ICDT), pages 131-142. OpenProceedings.org, 2014. URL: http://dx.doi.org/10.5441/002/icdt.2014.16.
  28. Maurizio Lenzerini. Ontology-based data management. In Proc. of the 20th Int. Conf. on Information and Knowledge Management (CIKM), pages 5-6, 2011. URL: http://dx.doi.org/10.1145/2063576.2063582.
  29. H. J. Levesque, R. Reiter, Y. Lesperance, F. Lin, and R. Scherl. GOLOG: A logic programming language for dynamic domains. J. of Logic Programming, 31:59-84, 1997. Google Scholar
  30. Leonid Libkin, Wim Martens, and Domagoj Vrgoc. Querying graph databases with XPath. In Proc. of the 16th Int. Conf. on Database Theory (ICDT), pages 129-140. ACMP, 2013. URL: http://dx.doi.org/10.1145/2448496.2448513.
  31. Hongkai Liu, Carsten Lutz, Maja Milicic, and Frank Wolter. Updating description logic ABoxes. In Proc. of the 10th Int. Conf. on the Principles of Knowledge Representation and Reasoning (KR), pages 46-56, 2006. Google Scholar
  32. Michael Mortimer. On languages with two variables. Zeitschrift für Mathematische Logik und Grundlagen der Mathematik, 21:135-140, 1975. Google Scholar
  33. Magdalena Ortiz. Ontology based query answering: The story so far. In Proc. of the 7th Alberto Mendelzon Int. Workshop on Foundations of Data Management (AMW), volume 1087 of CEUR Electronic Workshop Proceedings, http://ceur-ws.org/, 2013.
  34. Antonella Poggi, Domenico Lembo, Diego Calvanese, Giuseppe De Giacomo, Maurizio Lenzerini, and Riccardo Rosati. Linking data to ontologies. J. on Data Semantics, X:133-173, 2008. URL: http://dx.doi.org/10.1007/978-3-540-77688-8_5.
  35. Klaus Schild. A correspondence theory for terminological logics: Preliminary report. In Proc. of the 12th Int. Joint Conf. on Artificial Intelligence (IJCAI), pages 466-471, 1991. Google Scholar
  36. Peter T. Wood. Query languages for graph databases. SIGMOD Record, 41(1):50-60, 2012. URL: http://dx.doi.org/10.1145/2206869.2206879.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact