ACM SIGMOD Anthology ACM SIGMOD dblp.uni-trier.de

Knowledgebase Transformations.

Gösta Grahne, Alberto O. Mendelzon, Peter Z. Revesz: Knowledgebase Transformations. PODS 1992: 246-260
@inproceedings{DBLP:conf/pods/GrahneMR92,
  author    = {G{\"o}sta Grahne and
               Alberto O. Mendelzon and
               Peter Z. Revesz},
  title     = {Knowledgebase Transformations},
  booktitle = {Proceedings of the Eleventh ACM SIGACT-SIGMOD-SIGART Symposium
               on Principles of Database Systems, June 2-4, 1992, San Diego,
               California},
  publisher = {ACM Press},
  year      = {1992},
  isbn      = {0-89791-519-4},
  pages     = {246-260},
  ee        = {http://doi.acm.org/10.1145/137097.137882, db/conf/pods/GrahneMR92.html},
  crossref  = {DBLP:conf/pods/92},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}
BibTeX

Abstract

We propose a language that expresses uniformly queries and updates on knowledgebases consisting of finite sets of relational structures. The language contains an operator that "inserts" arbitrary first-order sentences into knowledgebase. The semantics of the insertion is based on the notion of update formalized by Katsuno and Mendelzon in the context of belief revision theory. Our language can express, among other things, hypothetical queries and queries on recursively indefinite databases. The expressive power of our language lies between existential second-order and general second-order queries. The data complexity is in general within exponential time, although it can be lowered to co-NP and to polynomial time by restricting the form of queries and updates.

Copyright © 1992 by the ACM, Inc., used by permission. Permission to make digital or hard copies is granted provided that copies are not made or distributed for profit or direct commercial advantage, and that copies show this notice on the first page or initial screen of a display along with the full citation.

Load The ACM SIGMOD Anthology, CDROM Edition, Volume 1-3, PODS '82-'98. and ... Load The ACM SIGMOD Anthology, Silver Edition, DVD 1, Proceedings. and ... BibTeX

Printed Edition

Proceedings of the Eleventh ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, June 2-4, 1992, San Diego, California. ACM Press 1992, ISBN 0-89791-519-4
Contents BibTeX

Online Edition: ACM Digital Library

[Abstract and Index Terms]
[Full Text in PDF Format, 1280 KB]

Journal Version

Gösta Grahne, Alberto O. Mendelzon, Peter Z. Revesz: Knowledgebase Transformations. J. Comput. Syst. Sci. 54(1): 98-112(1997) BibTeX

References

[AbG85]
Serge Abiteboul, Gösta Grahne: Update Semantics for Incomplete Databases. VLDB 1985: 1-12 BibTeX
[ASV90]
Serge Abiteboul, Eric Simon, Victor Vianu: Non-Deterministic Languages to Express Deterministic Transformations. PODS 1990: 218-229 BibTeX
[AGM85]
...
[ABW88]
...
[BS81]
François Bancilhon, Nicolas Spyratos: Update Semantics of Relational Views. ACM Trans. Database Syst. 6(4): 557-575(1981) BibTeX
[Bon88]
Anthony J. Bonner: Hypothetical Datalog: Complexity and Expressiblity. ICDT 1988: 144-160 BibTeX
[CH82]
Ashok K. Chandra, David Harel: Structure and Complexity of Relational Queries. J. Comput. Syst. Sci. 25(1): 99-128(1982) BibTeX
[EG92]
Thomas Eiter, Georg Gottlob: On the Complexity of Propositional Knowledge Base Revision, Updates, and Counterfactuals. PODS 1992: 261-273 BibTeX
[Fre91]
Karen A. Frenkel: The Human Genome Project and Informatics. Commun. ACM 34(11): 40-51(1991) BibTeX
[FUV83]
Ronald Fagin, Jeffrey D. Ullman, Moshe Y. Vardi: On the Semantics of Updates in Databases. PODS 1983: 352-365 BibTeX
[Gab85]
Dov M. Gabbay: N-Prolog: An Extension of Prolog with Hypothetical Implication II - Logical Foundations, and Negation as Failure. J. Log. Program. 2(4): 251-283(1985) BibTeX
[Gär86]
...
[Gär88]
...
[Gra91]
Gösta Grahne: Updates and Counterfactuals. KR 1991: 269-276 BibTeX
[GM91]
...
[HV91]
Joseph Y. Halpern, Moshe Y. Vardi: Model Checking vs. Theorem Proving: A Manifesto. KR 1991: 325-334 BibTeX
[IN88]
Tomasz Imielinski, Shamim A. Naqvi: Explicit Control of Logic Programs Through Rule Algebra. PODS 1988: 103-116 BibTeX
[Kan90]
...
[KM91a]
Hirofumi Katsuno, Alberto O. Mendelzon: On the Difference between Updating a Knowledge Base and Revising It. KR 1991: 387-394 BibTeX
[KM91b]
Hirofumi Katsuno, Alberto O. Mendelzon: Propositional Knowledge Base Revision and Minimal Change. Artif. Intell. 52(3): 263-294(1992) BibTeX
[LM81]
E. W. Leggett Jr., Daniel J. Moore: Optimization Problems and the Polynomial Hierarchy. Theor. Comput. Sci. 15: 279-289(1981) BibTeX
[Mak85]
...
[McC68]
...
[McC80]
...
[Mey90]
Ron van der Meyden: Recursively Indefinite Databases. ICDT 1990: 364-378 BibTeX
[Min82]
Jack Minker: On Indefinite Databases and the Closed World Assumption. CADE 1982: 292-308 BibTeX
[Rei78]
...
[Rei84]
...
[Rei92]
Raymond Reiter: On Formalizing Database Updates: Preliminary Report. EDBT 1992: 10-20 BibTeX
[Var82]
Moshe Y. Vardi: The Complexity of Relational Query Languages (Extended Abstract). STOC 1982: 137-146 BibTeX
[Win89]
Marianne Winslett: Reasoning about Action Using a Possible Models Approach. AAAI 1988: 89-93 BibTeX

Referenced by

  1. Serge Abiteboul, Richard Hull, Victor Vianu: Foundations of Databases. Addison-Wesley 1995, ISBN 0-201-53771-0
    Contents
  2. Peter Z. Revesz: On the Semantics of Theory Change: Arbitration between Old and New Information. PODS 1993: 71-82
  3. Dominique Laurent, Viet Phan Luong, Nicolas Spyratos: Updating Intensional Predicates in Deductive Databases. ICDE 1993: 14-21
BibTeX
ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]
ACM SIGMOD Anthology: Copyright © by ACM (info@acm.org), Corrections: anthology@acm.org
DBLP: Copyright © by Michael Ley (ley@uni-trier.de), last change: Sat May 16 23:34:06 2009