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}
}

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 ...

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 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML

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) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML

References

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

Home | Conferences | Journals | Series | FAQ — Search: Faceted | Complete | Author
Copyright © Fri Mar 12 17:19:56 2010 by Michael Ley (ley@uni-trier.de)