Limit Datalog: A declarative query language for data analysis
Motivated by applications in declarative data analysis, we study DatalogZ-an extension of Datalog with stratified negation and arithmetics over integers. Reasoning in this language is undecidable, so we present a fragment, called limit DatalogZ, that is powerful enough to naturally capture many impo...
| Հիմնական հեղինակներ: | , , , , |
|---|---|
| Ձևաչափ: | Journal article |
| Լեզու: | English |
| Հրապարակվել է: |
Association for Computing Machinery
2020
|
| _version_ | 1826292691634225152 |
|---|---|
| author | Grau, BC Horrocks, I Kaminski, M Kostylev, EV Motik, B |
| author_facet | Grau, BC Horrocks, I Kaminski, M Kostylev, EV Motik, B |
| author_sort | Grau, BC |
| collection | OXFORD |
| description | Motivated by applications in declarative data analysis, we study DatalogZ-an extension of Datalog with stratified negation and arithmetics over integers. Reasoning in this language is undecidable, so we present a fragment, called limit DatalogZ, that is powerful enough to naturally capture many important data analysis tasks. In limit DatalogZ, all intensional predicates with a numeric argument are limit predicates that keep only the maximal or minimal bounds on numeric values. Reasoning in limit DatalogZ is decidable if multiplication is used in a way that satisfies our linearity condition. Moreover, fact entailment in limit-linear DatalogZ is ΔEXP 2 -complete in combined and ΔP2 -complete in data complexity, and it drops to coNEXP and coNP, respectively, if only (semi-)positive programs are considered. We also propose an additional stability requirement, for which the complexity drops to EXP and P, matching the bounds for usual Datalog. Limit DatalogZ thus provides us with a unified logical framework for declarative data analysis and can be used as a basis for understanding the expressive power of the key data analysis constructs. |
| first_indexed | 2024-03-07T03:18:36Z |
| format | Journal article |
| id | oxford-uuid:b6adc6e9-7a11-4a15-8bdf-4d1b844f5fcd |
| institution | University of Oxford |
| language | English |
| last_indexed | 2024-03-07T03:18:36Z |
| publishDate | 2020 |
| publisher | Association for Computing Machinery |
| record_format | dspace |
| spelling | oxford-uuid:b6adc6e9-7a11-4a15-8bdf-4d1b844f5fcd2022-03-27T04:42:39ZLimit Datalog: A declarative query language for data analysisJournal articlehttp://purl.org/coar/resource_type/c_dcae04bcuuid:b6adc6e9-7a11-4a15-8bdf-4d1b844f5fcdEnglishSymplectic ElementsAssociation for Computing Machinery2020Grau, BCHorrocks, IKaminski, MKostylev, EVMotik, BMotivated by applications in declarative data analysis, we study DatalogZ-an extension of Datalog with stratified negation and arithmetics over integers. Reasoning in this language is undecidable, so we present a fragment, called limit DatalogZ, that is powerful enough to naturally capture many important data analysis tasks. In limit DatalogZ, all intensional predicates with a numeric argument are limit predicates that keep only the maximal or minimal bounds on numeric values. Reasoning in limit DatalogZ is decidable if multiplication is used in a way that satisfies our linearity condition. Moreover, fact entailment in limit-linear DatalogZ is ΔEXP 2 -complete in combined and ΔP2 -complete in data complexity, and it drops to coNEXP and coNP, respectively, if only (semi-)positive programs are considered. We also propose an additional stability requirement, for which the complexity drops to EXP and P, matching the bounds for usual Datalog. Limit DatalogZ thus provides us with a unified logical framework for declarative data analysis and can be used as a basis for understanding the expressive power of the key data analysis constructs. |
| spellingShingle | Grau, BC Horrocks, I Kaminski, M Kostylev, EV Motik, B Limit Datalog: A declarative query language for data analysis |
| title | Limit Datalog: A declarative query language for data analysis |
| title_full | Limit Datalog: A declarative query language for data analysis |
| title_fullStr | Limit Datalog: A declarative query language for data analysis |
| title_full_unstemmed | Limit Datalog: A declarative query language for data analysis |
| title_short | Limit Datalog: A declarative query language for data analysis |
| title_sort | limit datalog a declarative query language for data analysis |
| work_keys_str_mv | AT graubc limitdatalogadeclarativequerylanguagefordataanalysis AT horrocksi limitdatalogadeclarativequerylanguagefordataanalysis AT kaminskim limitdatalogadeclarativequerylanguagefordataanalysis AT kostylevev limitdatalogadeclarativequerylanguagefordataanalysis AT motikb limitdatalogadeclarativequerylanguagefordataanalysis |