DROPS

Document

DOI: 10.4230/LIPIcs.ICLP.2011.151

Declarative Output by Ordering Text Pieces

Authors: Stefan Brass

Published in: LIPIcs, Volume 11, Technical Communications of the 27th International Conference on Logic Programming (ICLP'11) (2011)

Abstract

Most real-world programs must produce output. If a deductive database is used to implement database application programs, it should be possible to specify the output declaratively. There is no generally accepted, completely satisfying solution for this. In this paper we propose to specify an output document by defining the position of text pieces (building blocks of the document). These text pieces are then ordered by their position and concatenated. This way of specifying output fits well to the bottom-up way of thinking about rules (from right to left) which is common in deductive databases. Of course, when evaluating such programs, one wants to avoid sorting operations as far as possible. We show how rules involving ordering can be efficiently implemented.

Cite as

Stefan Brass. Declarative Output by Ordering Text Pieces. In Technical Communications of the 27th International Conference on Logic Programming (ICLP'11). Leibniz International Proceedings in Informatics (LIPIcs), Volume 11, pp. 151-161, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2011)

Copy BibTex To Clipboard

@InProceedings{brass:LIPIcs.ICLP.2011.151,
  author =	{Brass, Stefan},
  title =	{{Declarative Output by Ordering Text Pieces}},
  booktitle =	{Technical Communications of the 27th International Conference on Logic Programming (ICLP'11)},
  pages =	{151--161},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-31-6},
  ISSN =	{1868-8969},
  year =	{2011},
  volume =	{11},
  editor =	{Gallagher, John P. and Gelfond, Michael},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICLP.2011.151},
  URN =		{urn:nbn:de:0030-drops-31770},
  doi =		{10.4230/LIPIcs.ICLP.2011.151},
  annote =	{Keywords: Deductive Databases, Logic Programming, Declarative Output, Bottom-Up Evaluation, Order, Sorting, Implementation}
}

Document

DOI: 10.4230/LIPIcs.ICLP.2010.44

Implementation Alternatives for Bottom-Up Evaluation

Authors: Stefan Brass

Published in: LIPIcs, Volume 7, Technical Communications of the 26th International Conference on Logic Programming (2010)

Abstract

Bottom-up evaluation is a central part of query evaluation / program execution in deductive databases. It is used after a source code optimization like magic sets or SLDmagic that ensures that only facts relevant for the query can be derived. Then bottom-up evaluation simply performs the iteration of the standard TP -operator to compute the minimal model. However, there are different ways to implement bottom-up evaluation efficiently. Since this is most critical for the performance of a deductive database system, and since performance is critical for the acceptance of deductive database technology, this question deserves a thorough analysis. In this paper we start this work by discussing several different implementation alternatives. Especially, we propose a new implementation of bottom-up evaluation called "Push-Method".

Cite as

Stefan Brass. Implementation Alternatives for Bottom-Up Evaluation. In Technical Communications of the 26th International Conference on Logic Programming. Leibniz International Proceedings in Informatics (LIPIcs), Volume 7, pp. 44-53, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)

Copy BibTex To Clipboard

@InProceedings{brass:LIPIcs.ICLP.2010.44,
  author =	{Brass, Stefan},
  title =	{{Implementation Alternatives for Bottom-Up Evaluation}},
  booktitle =	{Technical Communications of the 26th International Conference on Logic Programming},
  pages =	{44--53},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-17-0},
  ISSN =	{1868-8969},
  year =	{2010},
  volume =	{7},
  editor =	{Hermenegildo, Manuel and Schaub, Torsten},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICLP.2010.44},
  URN =		{urn:nbn:de:0030-drops-25820},
  doi =		{10.4230/LIPIcs.ICLP.2010.44},
  annote =	{Keywords: Deductive databases, bottom-up evaluation, implementation}
}

Search Results

Documents authored by Brass, Stefan

Declarative Output by Ordering Text Pieces

Abstract

Cite as

Implementation Alternatives for Bottom-Up Evaluation

Abstract

Cite as

Thanks for your feedback!

Could not send message