Document Open Access Logo

Input-Output Disjointness for Forward Expressions in the Logic of Information Flows

Authors Heba Aamer , Jan Van den Bussche

PDF

File

Thumbnail PDF
PDF
LIPIcs.ICDT.2021.8.pdf
  • Filesize: 0.69 MB
  • 18 pages

Document Identifiers

Subject Classification

ACM Subject Classification
  • Software and its engineering → Semantics
  • Software and its engineering → Data flow languages
  • Theory of computation → Database query languages (principles)
Keywords
  • Composition
  • expressive power
  • variable substitution

Metrics

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

Abstract

Last year we introduced the logic FLIF (forward logic of information flows) as a declarative language for specifying complex compositions of information sources with limited access patterns. The key insight of this approach is to view a system of information sources as a graph, where the nodes are valuations of variables, so that accesses to information sources can be modeled as edges in the graph. This allows the use of XPath-like navigational graph query languages. Indeed, a well-behaved fragment of FLIF, called io-disjoint FLIF, was shown to be equivalent to the executable fragment of first-order logic. It remained open, however, how io-disjoint FLIF compares to general FLIF . In this paper we close this gap by showing that general FLIF expressions can always be put into io-disjoint form.

Cite As Get BibTex

Heba Aamer and Jan Van den Bussche. Input-Output Disjointness for Forward Expressions in the Logic of Information Flows. In 24th International Conference on Database Theory (ICDT 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 186, pp. 8:1-8:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021) https://doi.org/10.4230/LIPIcs.ICDT.2021.8

Author Details

Heba Aamer
  • Hasselt University, Belgium
Jan Van den Bussche
  • Hasselt University, Belgium

Funding

This work was partially supported by Artificial Intelligence Research Flanders.
  • Aamer, Heba: Supported by the Special Research Fund (BOF) (BOF19OWB16).
  • Van den Bussche, Jan: Partially supported by the National Natural Science Foundations of China (61972455).

Acknowledgements

Thanks to Eugenia Ternovska for introducing us to LIF and to Bart Bogaerts for initial discussions on the topic of this paper.

References

  1. H. Aamer, B. Bogaerts, D. Surinx, E. Ternovska, and J. Van den Bussche. Executable first-order queries in the logic of information flows. In C. Lutz and J.C. Jung, editors, Proceedings 23rd International Conference on Database Theory, volume 155 of Leibniz International Proceedings in Informatics, pages 4:1-4:14. Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2020. Google Scholar
  2. H. Aamer, B. Bogaerts, D. Surinx, E. Ternovska, and J. Van den Bussche. Inputs, outputs, and composition in the logic of information flows. In D. Calvanese, E. Erdem, and M. Thielscher, editors, Proceedings 17th International Conference on Principles of Knowledge Representation and Reasoning. IJCAI Organization, 2020. Google Scholar
  3. H. Andréka, S. Givant, and I. Németi. Decision problems for equational theories of relation algebras, volume 126 of Memoirs of the American Mathematical Society. American Mathematical Society, 1997. Google Scholar
  4. R. Angles, M. Arenas, P. Barceló, A. Hogan, J. Reutter, and D. Vrgoč. Foundations of modern query languages for graph databases. ACM Computing Surveys, 50(5):68:1-68:40, 2017. Google Scholar
  5. R. Angles, P. Barceló, and G. Rios. A practical query language for graph DBs. In L. Bravo and M. Lenzerini, editors, Proceedings 7th Alberto Mendelzon International Workshop on Foundations of Data Management, volume 1087 of CEUR Workshop Proceedings, 2013. Google Scholar
  6. M. Bauderon and B. Courcelle. Graph expressions and graph rewritings. Mathematical Systems Theory, 20:83-127, 1987. Google Scholar
  7. M. Benedikt, J. Leblay, B. ten Cate, and E. Tsamoura. Generating Plans from Proofs: The Interpolation-based Approach to Query Reformulation. Morgan & Claypool, 2016. Google Scholar
  8. L. Cardelli, Ph. Gardner, and G. Ghelli. A spatial logic for querying graphs. In P. Widmayer et al., editors, Proceedings 29th International Colloquium on Automata, Languages and Programming, volume 2380 of Lecture Notes in Computer Science, pages 597-610. Springer, 2002. Google Scholar
  9. G.H.L. Fletcher, M. Gyssens, D. Leinders, D. Surinx, J. Van den Bussche, D. Van Gucht, S. Vansummeren, and Y. Wu. Relative expressive power of navigational querying on graphs. Information Sciences, 298:390-406, 2015. Google Scholar
  10. L. Libkin, W. Martens, and D. Vrgoč. Quering graph databases with XPath. In W.-C. Tan et al., editors, Proceedings 16th International Conference on Database Theory, pages 129-140. ACM, 2013. Google Scholar
  11. V. Lifschitz. Formal theories of action (preliminary report). In J.P. McDermott, editor, Proceedings 10th International Joint Conference on Artificial Intelligence, pages 966-972. Morgan Kaufmann, 1987. Google Scholar
  12. J. McCarthy and P.J. Hayes. Some philosophical problems from the standpoint of artificial intelligence. In B. Meltzer and D. Michie, editors, Machine Intelligence 4, pages 463-502. Edinburgh University Press, 1969. Google Scholar
  13. R. Milner. Communicating and Mobile Systems: The π-calculus. Cambridge University Press, 1999. Google Scholar
  14. A. Nash and B. Ludäscher. Processing first-order queries under limited access patterns. In Proceedings 23th ACM Symposium on Principles of Database Systems, pages 307-318, 2004. Google Scholar
  15. J. Pérez, M. Arenas, and C. Gutierrez. nSPARQL: A navigational language for RDF. Journal of Web Semantics, 8(4):255-270, 2010. Google Scholar
  16. D. Surinx, G.H.L. Fletcher, M. Gyssens, D. Leinders, J. Van den Bussche, D. Van Gucht, S. Vansummeren, and Y. Wu. Relative expressive power of navigational querying on graphs using transitive closure. Logic Journal of the IGPL, 23(5):759-788, 2015. Google Scholar
  17. E. Ternovska. Recent progress on the algebra of modular systems. In J.L. Reutter and D. Srivastava, editors, Proceedings 11th Alberto Mendelzon International Workshop on Foundations of Data Management, volume 1912 of CEUR Workshop Proceedings, 2017. Google Scholar
  18. E. Ternovska. An algebra of modular systems: static and dynamic perspectives. In A. Herzig and A. Popescu, editors, Frontiers of Combining Systems: Proceedings 12th FroCos, volume 11715 of Lecture Notes in Artificial Intelligence, pages 94-111. Springer, 2019. Google Scholar
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-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact