On the computational aspect of rule based database updates

Yun Bai; Yan Zhang

doi:10.1007/3-540-45517-5_9

On the computational aspect of rule based database updates

Yun Bai, Yan Zhang

School of Computer, Data & Mathematical Sciences

Research output: Chapter in Book / Conference Paper › Conference Paper › peer-review

1 Citation (Scopus)

Abstract

We develop a general framework of rule based database update on the basis of prioritized logic programs. This approach has advantages in representing and handling information conflict in updates. We then focus on the computational aspect of this approach. We show that under our framework, the model checking in an update is Π^P₂-complete, while the associated inference problem is [Formula presented] -complete. From a practical viewpoint, we propose two strategies to simplify an update specification so that under some conditions, solving an update problem can be based on solving some smaller components of the original problem. Our experimental result shows that these strategies indeed significantly reduce the time cost of evaluating an update specification.

Original language	English
Title of host publication	Engineering of Intelligent Systems - 14th International Conference on Industrial and Engineering Applications of Artificial Intelligence and Expert Systems, IEA/AIE 2001, Proceedings
Editors	Laszlo Monostori, Jozsef Vancza, Moonis Ali
Publisher	Springer Verlag
Pages	71-81
Number of pages	11
ISBN (Print)	3540422196, 9783540422198
DOIs	https://doi.org/10.1007/3-540-45517-5_9
Publication status	Published - 2001
Event	14th International Conference on Industrial and Engineering Applications of Artificial Intelligence and Expert Systems, IEA/AIE 2001 - Budapest, Hungary Duration: 4 Jun 2001 → 7 Jun 2001

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	2070
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	14th International Conference on Industrial and Engineering Applications of Artificial Intelligence and Expert Systems, IEA/AIE 2001
Country/Territory	Hungary
City	Budapest
Period	4/06/01 → 7/06/01

Bibliographical note

Publisher Copyright:
© Springer-Verlag Berlin Heidelberg 2001.

Keywords

Automated problem solving
Intelligent databases
Knowledge representation

Access to Document

10.1007/3-540-45517-5_9

Cite this

Bai, Y., & Zhang, Y. (2001). On the computational aspect of rule based database updates. In L. Monostori, J. Vancza, & M. Ali (Eds.), Engineering of Intelligent Systems - 14th International Conference on Industrial and Engineering Applications of Artificial Intelligence and Expert Systems, IEA/AIE 2001, Proceedings (pp. 71-81). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 2070). Springer Verlag. https://doi.org/10.1007/3-540-45517-5_9

Bai, Yun ; Zhang, Yan. / On the computational aspect of rule based database updates. Engineering of Intelligent Systems - 14th International Conference on Industrial and Engineering Applications of Artificial Intelligence and Expert Systems, IEA/AIE 2001, Proceedings. editor / Laszlo Monostori ; Jozsef Vancza ; Moonis Ali. Springer Verlag, 2001. pp. 71-81 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{1839f8662b194b1aa602bc15855e8617,

title = "On the computational aspect of rule based database updates",

abstract = "We develop a general framework of rule based database update on the basis of prioritized logic programs. This approach has advantages in representing and handling information conflict in updates. We then focus on the computational aspect of this approach. We show that under our framework, the model checking in an update is ΠP2-complete, while the associated inference problem is [Formula presented] -complete. From a practical viewpoint, we propose two strategies to simplify an update specification so that under some conditions, solving an update problem can be based on solving some smaller components of the original problem. Our experimental result shows that these strategies indeed significantly reduce the time cost of evaluating an update specification.",

keywords = "Automated problem solving, Intelligent databases, Knowledge representation",

author = "Yun Bai and Yan Zhang",

note = "Publisher Copyright: {\textcopyright} Springer-Verlag Berlin Heidelberg 2001.; 14th International Conference on Industrial and Engineering Applications of Artificial Intelligence and Expert Systems, IEA/AIE 2001 ; Conference date: 04-06-2001 Through 07-06-2001",

year = "2001",

doi = "10.1007/3-540-45517-5_9",

language = "English",

isbn = "3540422196",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "71--81",

editor = "Laszlo Monostori and Jozsef Vancza and Moonis Ali",

booktitle = "Engineering of Intelligent Systems - 14th International Conference on Industrial and Engineering Applications of Artificial Intelligence and Expert Systems, IEA/AIE 2001, Proceedings",

}

Bai, Y & Zhang, Y 2001, On the computational aspect of rule based database updates. in L Monostori, J Vancza & M Ali (eds), Engineering of Intelligent Systems - 14th International Conference on Industrial and Engineering Applications of Artificial Intelligence and Expert Systems, IEA/AIE 2001, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 2070, Springer Verlag, pp. 71-81, 14th International Conference on Industrial and Engineering Applications of Artificial Intelligence and Expert Systems, IEA/AIE 2001, Budapest, Hungary, 4/06/01. https://doi.org/10.1007/3-540-45517-5_9

On the computational aspect of rule based database updates. / Bai, Yun ; Zhang, Yan.
Engineering of Intelligent Systems - 14th International Conference on Industrial and Engineering Applications of Artificial Intelligence and Expert Systems, IEA/AIE 2001, Proceedings. ed. / Laszlo Monostori; Jozsef Vancza; Moonis Ali. Springer Verlag, 2001. p. 71-81 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 2070).

Research output: Chapter in Book / Conference Paper › Conference Paper › peer-review

TY - GEN

T1 - On the computational aspect of rule based database updates

AU - Bai, Yun

AU - Zhang, Yan

N1 - Publisher Copyright: © Springer-Verlag Berlin Heidelberg 2001.

PY - 2001

Y1 - 2001

N2 - We develop a general framework of rule based database update on the basis of prioritized logic programs. This approach has advantages in representing and handling information conflict in updates. We then focus on the computational aspect of this approach. We show that under our framework, the model checking in an update is ΠP2-complete, while the associated inference problem is [Formula presented] -complete. From a practical viewpoint, we propose two strategies to simplify an update specification so that under some conditions, solving an update problem can be based on solving some smaller components of the original problem. Our experimental result shows that these strategies indeed significantly reduce the time cost of evaluating an update specification.

AB - We develop a general framework of rule based database update on the basis of prioritized logic programs. This approach has advantages in representing and handling information conflict in updates. We then focus on the computational aspect of this approach. We show that under our framework, the model checking in an update is ΠP2-complete, while the associated inference problem is [Formula presented] -complete. From a practical viewpoint, we propose two strategies to simplify an update specification so that under some conditions, solving an update problem can be based on solving some smaller components of the original problem. Our experimental result shows that these strategies indeed significantly reduce the time cost of evaluating an update specification.

KW - Automated problem solving

KW - Intelligent databases

KW - Knowledge representation

UR - http://www.scopus.com/inward/record.url?scp=0009217919&partnerID=8YFLogxK

U2 - 10.1007/3-540-45517-5_9

DO - 10.1007/3-540-45517-5_9

M3 - Conference Paper

AN - SCOPUS:0009217919

SN - 3540422196

SN - 9783540422198

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 71

EP - 81

BT - Engineering of Intelligent Systems - 14th International Conference on Industrial and Engineering Applications of Artificial Intelligence and Expert Systems, IEA/AIE 2001, Proceedings

A2 - Monostori, Laszlo

A2 - Vancza, Jozsef

A2 - Ali, Moonis

PB - Springer Verlag

T2 - 14th International Conference on Industrial and Engineering Applications of Artificial Intelligence and Expert Systems, IEA/AIE 2001

Y2 - 4 June 2001 through 7 June 2001

ER -

Bai Y , Zhang Y. On the computational aspect of rule based database updates. In Monostori L, Vancza J, Ali M, editors, Engineering of Intelligent Systems - 14th International Conference on Industrial and Engineering Applications of Artificial Intelligence and Expert Systems, IEA/AIE 2001, Proceedings. Springer Verlag. 2001. p. 71-81. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/3-540-45517-5_9

On the computational aspect of rule based database updates

Abstract

Publication series

Conference

Bibliographical note

Keywords

Access to Document

Other files and links

Fingerprint

Cite this