Article

Free access

Specification and implementation of programs for updating incomplete information databases

Author:

S. HegnerAuthors Info & Claims

PODS '87: Proceedings of the sixth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems

Pages 146 - 158

https://doi.org/10.1145/28659.28675

Published: 01 June 1987 Publication History

Abstract

The problem of updating incomplete information databases is examined as a programming problem. From this point of view formal denotational semantics are developed for two applicative programming languages, BLU and HLU. BLU is a very simple language with only five primitives, and is designed primarily as a tool for the implementation of higher level languages. The semantics of BLU are formally developed at two levels possible worlds and clausal and the latter is shown to be a correct implementation of the former. HLU is a user level update language. It is defined entirely in terms of BLU, and so immediately inherits its semantic definition from that language. This demonstrates a level of completeness for BLU as a level of primitives for update language implementation. The necessity of a particular BLU primitive, masking, suggests that there is a high degree of inherent complexity in updating logical databases.

References

[1]

Abtteboul and G Grahne, 'Update semantics for mcornplete databases', ~n Proc 1985 VLDB Conference, 1-12

[2]

Chung and R C Lee, Symbohc Logic and Mechanical Theorem Prowng, Academic Press 1973

Digital Library

[3]

K L Clark 'Negation as failure', in Loglc and Data Bases, H GaUalre and J Minker (editor) Plenum Press, 1978 293 322

[4]

E F Codd, "Relational completeness of database sublanguages, jn Data Base Systems R Rustm (editor), Prentice-Hall, 1972, 65-98

[5]

H Ehrlg and B Mahr, Fundamentals of Algebraic Specification 1, Springer-Verlag, 1985

Digital Library

[6]

H B Enderton A Mathematical Introduction to Logic Academic Press 1972

[7]

R Fagm, G M Kuper, J D UIimanandM Y Vardl, 'Updating Logical Databases, m Advances in Computing Research, vot 3, The Theory of Databases P Kanellakls (edItor), JAI Press, 1986, 1-18

[8]

H Gallalre, J Minker and J M Nicolas, Logic arid databases a deduchve approach, ACM Computing Surveys 16, 2 (1984), 153-185

Digital Library

[9]

S J Hegner, Relabonal Database Decomposlt~on Logical and Algebralc Foundabons, monograph in preparabon, to appear, 1987

[10]

R Hull, "Finitely specifiable Imphcahonal Dependency Famdies", J ACM 31, 2 (1984), 210- 226

Digital Library

[11]

T Imlehr~skf, "On algebraic query processing m Iogtcal databases", ~n Advances ~n Data Base Theory, vol 2, H Gallalre, J Mmker and J M NIcolas (eddor), Plenum Press 1984, 285-318

[12]

T im~etmskf and W Lfpskl Jr,' Incomplete information in relahonal databases ', j ACM 31 (1984) 761 791

Digital Library

[13]

B E Jacobs, On database logic, J ACM 29, 2 (1982) 310-332

Digital Library

[14]

B E Jacobs, A R Aronson and A C Klug, 'On mterpretahons of relational languages and solut,ons to the ~mplf~d constraint problem ', ACM Trans Database Systems 7, 2 (1982), 291-315

Digital Library

[15]

A Keller and M W Wdklns, 'Approaches for updating databases incomplete mformat~on with nulls", ~n Proc International Conference on Database Engineenng, 24-27 Aprd 1984, 332-340

Digital Library

[16]

H J Levesque, 'The Logic of incomplete Knowledge Bases", in On Conceptual Modelling, M L Brodae, J Mylopoulos and J W Schmldt (edrtor), Sprmger-Verlag, 1984, 165-186

[17]

E G Manes and M A Arbib, Algebraic Approaches to Program Semantics Springer- Verlag, 1986

Digital Library

[18]

J R McSklmm and J Mmker, 'A predicate calculus based semanhc network for deducttve searching ', m Assoc~at;ve Networks, N V Fmdler (editor), Academic Press 1979, 205 238

[19]

J Rees and W Clinger 'Rewsed3 report on the algorithmic language Scheme, SIGPLAN Nobces Notices 21 12 (December 1986), 37-79

Digital Library

[20]

R Re~ter Towards a logical reconstruchon of relational database theory, ~n On Conceptual Model#ng M L Brodle J Mylopoulos and J W Schmfdt (editor), Sprmger-Verlag, 1984, 191-238

[21]

7"1 Scheme Language Reference Manual, Texas Instruments, Inc, 1985

[22]

M W W=lk=ns, 'A model theorebc approach to updating log=cal databases ', Report No STAN-CS- 86-1096, Department of Computer Scmence, Stanford Un,rersfly January 1986

[23]

P H Winston and B K P Horn, L~sp Second edition, Addison-Wesley 1984

Cited By

Mohamed RLoukil ZGargouri FBouraoui Z(2023)Revision of prioritized $$\mathcal {E}\mathcal {L}$$ ontologiesApplied Intelligence10.1007/s10489-023-05074-653:24(30359-30383)Online publication date: 17-Nov-2023
https://doi.org/10.1007/s10489-023-05074-6
Fang LWan HLiu XFang BLai ZMcIlraith SWeinberger K(2018)Dependence in propositional logicProceedings of the Thirty-Second AAAI Conference on Artificial Intelligence and Thirtieth Innovative Applications of Artificial Intelligence Conference and Eighth AAAI Symposium on Educational Advances in Artificial Intelligence10.5555/3504035.3504259(1835-1844)Online publication date: 2-Feb-2018
https://dl.acm.org/doi/10.5555/3504035.3504259
Slota MLeite JSwift T(2015)On updates of hybrid knowledge bases composed of ontologies and rulesArtificial Intelligence10.1016/j.artint.2015.07.008229:C(33-104)Online publication date: 1-Dec-2015
https://dl.acm.org/doi/10.1016/j.artint.2015.07.008
Show More Cited By

Index Terms

Specification and implementation of programs for updating incomplete information databases

Recommendations

Updating databases with incomplete information
A grounded specification language for agent programs
AAMAS '07: Proceedings of the 6th international joint conference on Autonomous agents and multiagent systems

This paper studies the relation between agent specification and agent programming languages. In particular, it shows that an agent programming language obeys some desirable properties expressed in an agent specification language, i.e., that any agent ...
Programming Language Specification and Implementation
Leveraging Applications of Formal Methods, Verification and Validation. Modeling
Abstract
The specification of a programming language is a special case of the specification of software in general. This paper discusses the relation between semantics and implementation, or specification and program, using two very different languages for ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

PODS '87: Proceedings of the sixth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems

June 1987

363 pages

ISBN:0897912233

DOI:10.1145/28659

Editor:
Moshe Y. Vardi

Copyright © 1987 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 June 1987

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

PODS '87

Sponsor:

PODS '87: Principles of database systems

March 23 - 25, 1987

California, San Diego, USA

Acceptance Rates

Overall Acceptance Rate 642 of 2,707 submissions, 24%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

16
Total Citations
View Citations
218
Total Downloads

Downloads (Last 12 months)35
Downloads (Last 6 weeks)3

Reflects downloads up to 30 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Mohamed RLoukil ZGargouri FBouraoui Z(2023)Revision of prioritized $$\mathcal {E}\mathcal {L}$$ ontologiesApplied Intelligence10.1007/s10489-023-05074-653:24(30359-30383)Online publication date: 17-Nov-2023
https://doi.org/10.1007/s10489-023-05074-6
Fang LWan HLiu XFang BLai ZMcIlraith SWeinberger K(2018)Dependence in propositional logicProceedings of the Thirty-Second AAAI Conference on Artificial Intelligence and Thirtieth Innovative Applications of Artificial Intelligence Conference and Eighth AAAI Symposium on Educational Advances in Artificial Intelligence10.5555/3504035.3504259(1835-1844)Online publication date: 2-Feb-2018
https://dl.acm.org/doi/10.5555/3504035.3504259
Slota MLeite JSwift T(2015)On updates of hybrid knowledge bases composed of ontologies and rulesArtificial Intelligence10.1016/j.artint.2015.07.008229:C(33-104)Online publication date: 1-Dec-2015
https://dl.acm.org/doi/10.1016/j.artint.2015.07.008
Zhu HZhang CCao ZTang RYang M(2014)An Efficient Conditioning Method for Probabilistic Relational DatabasesWeb-Age Information Management10.1007/978-3-319-08010-9_25(225-236)Online publication date: 2014
https://doi.org/10.1007/978-3-319-08010-9_25
Sarma ATheobald MWidom J(2010)LIVEProceedings of the 22nd international conference on Scientific and statistical database management10.5555/1876037.1876072(416-433)Online publication date: 30-Jun-2010
https://dl.acm.org/doi/10.5555/1876037.1876072
Das Sarma ATheobald MWidom J(2010)LIVE: A Lineage-Supported Versioned DBMSScientific and Statistical Database Management10.1007/978-3-642-13818-8_29(416-433)Online publication date: 2010
https://doi.org/10.1007/978-3-642-13818-8_29
Cerro LHerzig A(2005)Metaprogramming through intensional deduction: Some examplesMeta-Programming in Logic10.1007/3-540-56282-6_2(11-25)Online publication date: 30-May-2005
https://doi.org/10.1007/3-540-56282-6_2
Tomasic A(2005)View update translation via deduction and annotationICDT '8810.1007/3-540-50171-1_22(338-352)Online publication date: 1-Jun-2005
https://doi.org/10.1007/3-540-50171-1_22
Lang JLiberatore PMarquis P(2003)Propositional independenceJournal of Artificial Intelligence Research10.5555/1622420.162243118:1(391-443)Online publication date: 1-May-2003
https://dl.acm.org/doi/10.5555/1622420.1622431
Meyden R(1998)Logical Approaches to Incomplete Information: A SurveyLogics for Databases and Information Systems10.1007/978-1-4615-5643-5_10(307-356)Online publication date: 1998
https://doi.org/10.1007/978-1-4615-5643-5_10
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Table of Contents