License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ICDT.2021.8
URN: urn:nbn:de:0030-drops-137167
Go to the corresponding LIPIcs Volume Portal

Aamer, Heba ; Van den Bussche, Jan

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

LIPIcs-ICDT-2021-8.pdf (0.7 MB)


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.

BibTeX - Entry

  author =	{Aamer, Heba and Van den Bussche, Jan},
  title =	{{Input-Output Disjointness for Forward Expressions in the Logic of Information Flows}},
  booktitle =	{24th International Conference on Database Theory (ICDT 2021)},
  pages =	{8:1--8:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-179-5},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{186},
  editor =	{Yi, Ke and Wei, Zhewei},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{},
  URN =		{urn:nbn:de:0030-drops-137167},
  doi =		{10.4230/LIPIcs.ICDT.2021.8},
  annote =	{Keywords: Composition, expressive power, variable substitution}

Keywords: Composition, expressive power, variable substitution
Collection: 24th International Conference on Database Theory (ICDT 2021)
Issue Date: 2021
Date of publication: 11.03.2021

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI