WEKO3
アイテム
{"_buckets": {"deposit": "efd3fbe0-01b5-4a5a-a984-c68f48cd1ace"}, "_deposit": {"created_by": 3, "id": "129", "owners": [3], "pid": {"revision_id": 0, "type": "depid", "value": "129"}, "status": "published"}, "_oai": {"id": "oai:kyutech.repo.nii.ac.jp:00000129", "sets": ["24"]}, "author_link": ["597"], "item_21_biblio_info_6": {"attribute_name": "書誌情報", "attribute_value_mlt": [{"bibliographicIssueDates": {"bibliographicIssueDate": "2005-12-02", "bibliographicIssueDateType": "Issued"}, "bibliographicIssueNumber": "1", "bibliographicPageEnd": "94", "bibliographicPageStart": "84", "bibliographicVolumeNumber": "348", "bibliographic_titles": [{"bibliographic_title": "Theoretical Computer Science"}]}]}, "item_21_description_4": {"attribute_name": "抄録", "attribute_value_mlt": [{"subitem_description": "A conjunctive query problem is a problem to determine whether or not a tuple belongsto the answer of a conjunctive query over a database. In this paper, a tuple,a conjunctive query and a database in relational database theory are regarded as aground atom, a nonrecursive function-free definite clause and a finite set of groundatoms, respectively, in inductive logic programming terminology. An acyclic conjunctivequery problem is a conjunctive query problem with acyclicity. Concernedwith the acyclic conjunctive query problem, in this paper, we present the hardnessresults of predicting acyclic conjunctive queries from an instance with a j-databaseof which predicate symbol is at most j-ary. Also we deal with two kinds of instances,a simple instance as a set of ground atoms and an extended instance as aset of pairs of a ground atom and a description. We mainly show that, from both asimple and an extended instances, acyclic conjunctive queries are not polynomialtimepredictable with j-databases (j ≥ 3) under the cryptographic assumptions,and predicting acyclic conjunctive queries with 2-databases is as hard as predictingDNF formulas. Hence, the acyclic conjunctive queries become a natural examplethat the equivalence between subsumption-efficiency and efficient pac-learnabilityfrom both a simple and an extended instances collapses.", "subitem_description_type": "Abstract"}]}, "item_21_description_60": {"attribute_name": "資源タイプ", "attribute_value_mlt": [{"subitem_description": "Journal Article", "subitem_description_type": "Other"}]}, "item_21_full_name_3": {"attribute_name": "著者別名", "attribute_value_mlt": [{"affiliations": [{"affiliationNames": [{"affiliationName": "", "lang": "ja"}], "nameIdentifiers": []}], "familyNames": [{"familyName": "Hirata", "familyNameLang": "en"}, {"familyName": "平田", "familyNameLang": "ja"}, {"familyName": "ヒラタ", "familyNameLang": "ja-Kana"}], "givenNames": [{"givenName": "Kouichi", "givenNameLang": "en"}, {"givenName": "耕一", "givenNameLang": "ja"}, {"givenName": "コウイチ", "givenNameLang": "ja-Kana"}], "nameIdentifiers": [{"nameIdentifier": "597", "nameIdentifierScheme": "WEKO"}, {"nameIdentifier": "20274558", "nameIdentifierScheme": "e-Rad", "nameIdentifierURI": "https://nrid.nii.ac.jp/ja/nrid/1000020274558"}, {"nameIdentifier": "55730619500", "nameIdentifierScheme": "Scopus著者ID", "nameIdentifierURI": "https://www.scopus.com/authid/detail.uri?authorId=55730619500"}, {"nameIdentifier": "189", "nameIdentifierScheme": "九工大研究者情報", "nameIdentifierURI": "https://hyokadb02.jimu.kyutech.ac.jp/html/189_ja.html"}], "names": [{"name": "Hirata, Kouichi", "nameLang": "en"}, {"name": "平田, 耕一", "nameLang": "ja"}, {"name": "ヒラタ, コウイチ", "nameLang": "ja-Kana"}]}]}, "item_21_publisher_7": {"attribute_name": "出版者", "attribute_value_mlt": [{"subitem_publisher": "Elsevier"}]}, "item_21_relation_12": {"attribute_name": "DOI", "attribute_value_mlt": [{"subitem_relation_type": "isVersionOf", "subitem_relation_type_id": {"subitem_relation_type_id_text": "https://doi.org/10.1016/j.tcs.2005.09.006", "subitem_relation_type_select": "DOI"}}]}, "item_21_relation_14": {"attribute_name": "情報源", "attribute_value_mlt": [{"subitem_relation_name": [{"subitem_relation_name_text": "http://www.sciencedirect.com/science/journal/03043975"}], "subitem_relation_type_id": {"subitem_relation_type_id_text": "http://www.sciencedirect.com/science/journal/03043975", "subitem_relation_type_select": "URI"}}]}, "item_21_rights_13": {"attribute_name": "権利", "attribute_value_mlt": [{"subitem_rights": "Copyright (c) 2005 Elsevier B.V."}]}, "item_21_select_59": {"attribute_name": "査読の有無", "attribute_value_mlt": [{"subitem_select_item": "yes"}]}, "item_21_source_id_8": {"attribute_name": "ISSN", "attribute_value_mlt": [{"subitem_source_identifier": "0304-3975", "subitem_source_identifier_type": "ISSN"}]}, "item_21_text_36": {"attribute_name": "著者所属", "attribute_value_mlt": [{"subitem_text_value": "Department of Artificial Intelligence, Kyushu Institute of Technology, Kawazu 680-4, Iizuka 820-8502, Japan"}]}, "item_21_version_type_58": {"attribute_name": "著者版フラグ", "attribute_value_mlt": [{"subitem_version_resource": "http://purl.org/coar/version/c_ab4af688f83e57aa", "subitem_version_type": "AM"}]}, "item_creator": {"attribute_name": "著者", "attribute_type": "creator", "attribute_value_mlt": [{"creatorAffiliations": [{"affiliationNameIdentifiers": [], "affiliationNames": [{"affiliationName": "", "affiliationNameLang": "ja"}]}], "creatorNames": [{"creatorName": "Hirata, Kouichi", "creatorNameLang": "en"}, {"creatorName": "平田, 耕一", "creatorNameLang": "ja"}, {"creatorName": "ヒラタ, コウイチ", "creatorNameLang": "ja-Kana"}], "familyNames": [{"familyName": "Hirata", "familyNameLang": "en"}, {"familyName": "平田", "familyNameLang": "ja"}, {"familyName": "ヒラタ", "familyNameLang": "ja-Kana"}], "givenNames": [{"givenName": "Kouichi", "givenNameLang": "en"}, {"givenName": "耕一", "givenNameLang": "ja"}, {"givenName": "コウイチ", "givenNameLang": "ja-Kana"}], "nameIdentifiers": [{"nameIdentifier": "597", "nameIdentifierScheme": "WEKO"}, {"nameIdentifier": "20274558", "nameIdentifierScheme": "e-Rad", "nameIdentifierURI": "https://nrid.nii.ac.jp/ja/nrid/1000020274558"}, {"nameIdentifier": "55730619500", "nameIdentifierScheme": "Scopus著者ID", "nameIdentifierURI": "https://www.scopus.com/authid/detail.uri?authorId=55730619500"}, {"nameIdentifier": "189", "nameIdentifierScheme": "九工大研究者情報", "nameIdentifierURI": "https://hyokadb02.jimu.kyutech.ac.jp/html/189_ja.html"}]}]}, "item_files": {"attribute_name": "ファイル情報", "attribute_type": "file", "attribute_value_mlt": [{"accessrole": "open_date", "date": [{"dateType": "Available", "dateValue": "2007-11-20"}], "displaytype": "detail", "download_preview_message": "", "file_order": 0, "filename": "j.tcs.2005.09.006.pdf", "filesize": [{"value": "172.6 kB"}], "format": "application/pdf", "future_date_message": "", "is_thumbnail": false, "licensetype": "license_free", "mimetype": "application/pdf", "size": 172600.0, "url": {"label": "j.tcs.2005.09.006.pdf", "url": "https://kyutech.repo.nii.ac.jp/record/129/files/j.tcs.2005.09.006.pdf"}, "version_id": "0996a0dc-d7c9-4183-82f2-b3bdcbc0add7"}]}, "item_keyword": {"attribute_name": "キーワード", "attribute_value_mlt": [{"subitem_subject": "acyclic conjunctive query", "subitem_subject_scheme": "Other"}, {"subitem_subject": "inductive logic programming", "subitem_subject_scheme": "Other"}, {"subitem_subject": "prediction", "subitem_subject_scheme": "Other"}, {"subitem_subject": "prediction-preserving reduction", "subitem_subject_scheme": "Other"}, {"subitem_subject": "subsumption", "subitem_subject_scheme": "Other"}]}, "item_language": {"attribute_name": "言語", "attribute_value_mlt": [{"subitem_language": "eng"}]}, "item_resource_type": {"attribute_name": "資源タイプ", "attribute_value_mlt": [{"resourcetype": "journal article", "resourceuri": "http://purl.org/coar/resource_type/c_6501"}]}, "item_title": "Prediction-hardness of acyclic conjunctive queries", "item_titles": {"attribute_name": "タイトル", "attribute_value_mlt": [{"subitem_title": "Prediction-hardness of acyclic conjunctive queries"}]}, "item_type_id": "21", "owner": "3", "path": ["24"], "permalink_uri": "http://hdl.handle.net/10228/373", "pubdate": {"attribute_name": "公開日", "attribute_value": "2007-11-20"}, "publish_date": "2007-11-20", "publish_status": "0", "recid": "129", "relation": {}, "relation_version_is_last": true, "title": ["Prediction-hardness of acyclic conjunctive queries"], "weko_shared_id": 3}
Prediction-hardness of acyclic conjunctive queries
http://hdl.handle.net/10228/373
http://hdl.handle.net/10228/3733ed9110b-585b-433b-ab0f-394960970862
名前 / ファイル | ライセンス | アクション |
---|---|---|
j.tcs.2005.09.006.pdf (172.6 kB)
|
|
Item type | 学術雑誌論文 = Journal Article(1) | |||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|
公開日 | 2007-11-20 | |||||||||||
資源タイプ | ||||||||||||
資源タイプ識別子 | http://purl.org/coar/resource_type/c_6501 | |||||||||||
資源タイプ | journal article | |||||||||||
タイトル | ||||||||||||
タイトル | Prediction-hardness of acyclic conjunctive queries | |||||||||||
言語 | ||||||||||||
言語 | eng | |||||||||||
著者 |
平田, 耕一
× 平田, 耕一
WEKO
597
|
|||||||||||
抄録 | ||||||||||||
内容記述タイプ | Abstract | |||||||||||
内容記述 | A conjunctive query problem is a problem to determine whether or not a tuple belongsto the answer of a conjunctive query over a database. In this paper, a tuple,a conjunctive query and a database in relational database theory are regarded as aground atom, a nonrecursive function-free definite clause and a finite set of groundatoms, respectively, in inductive logic programming terminology. An acyclic conjunctivequery problem is a conjunctive query problem with acyclicity. Concernedwith the acyclic conjunctive query problem, in this paper, we present the hardnessresults of predicting acyclic conjunctive queries from an instance with a j-databaseof which predicate symbol is at most j-ary. Also we deal with two kinds of instances,a simple instance as a set of ground atoms and an extended instance as aset of pairs of a ground atom and a description. We mainly show that, from both asimple and an extended instances, acyclic conjunctive queries are not polynomialtimepredictable with j-databases (j ≥ 3) under the cryptographic assumptions,and predicting acyclic conjunctive queries with 2-databases is as hard as predictingDNF formulas. Hence, the acyclic conjunctive queries become a natural examplethat the equivalence between subsumption-efficiency and efficient pac-learnabilityfrom both a simple and an extended instances collapses. | |||||||||||
書誌情報 |
Theoretical Computer Science 巻 348, 号 1, p. 84-94, 発行日 2005-12-02 |
|||||||||||
出版社 | ||||||||||||
出版者 | Elsevier | |||||||||||
DOI | ||||||||||||
関連タイプ | isVersionOf | |||||||||||
識別子タイプ | DOI | |||||||||||
関連識別子 | https://doi.org/10.1016/j.tcs.2005.09.006 | |||||||||||
ISSN | ||||||||||||
収録物識別子タイプ | ISSN | |||||||||||
収録物識別子 | 0304-3975 | |||||||||||
著作権関連情報 | ||||||||||||
権利情報 | Copyright (c) 2005 Elsevier B.V. | |||||||||||
キーワード | ||||||||||||
主題Scheme | Other | |||||||||||
主題 | acyclic conjunctive query | |||||||||||
キーワード | ||||||||||||
主題Scheme | Other | |||||||||||
主題 | inductive logic programming | |||||||||||
キーワード | ||||||||||||
主題Scheme | Other | |||||||||||
主題 | prediction | |||||||||||
キーワード | ||||||||||||
主題Scheme | Other | |||||||||||
主題 | prediction-preserving reduction | |||||||||||
キーワード | ||||||||||||
主題Scheme | Other | |||||||||||
主題 | subsumption | |||||||||||
出版タイプ | ||||||||||||
出版タイプ | AM | |||||||||||
出版タイプResource | http://purl.org/coar/version/c_ab4af688f83e57aa | |||||||||||
査読の有無 | ||||||||||||
値 | yes | |||||||||||
資料タイプ | ||||||||||||
内容記述タイプ | Other | |||||||||||
内容記述 | Journal Article | |||||||||||
著者別名 | ||||||||||||
姓名 | Hirata, Kouichi | |||||||||||
言語 | en | |||||||||||
姓名 | 平田, 耕一 | |||||||||||
言語 | ja | |||||||||||
姓名 | ヒラタ, コウイチ | |||||||||||
言語 | ja-Kana | |||||||||||
著者所属 | ||||||||||||
Department of Artificial Intelligence, Kyushu Institute of Technology, Kawazu 680-4, Iizuka 820-8502, Japan | ||||||||||||
情報源 | ||||||||||||
識別子タイプ | URI | |||||||||||
関連識別子 | http://www.sciencedirect.com/science/journal/03043975 | |||||||||||
関連名称 | http://www.sciencedirect.com/science/journal/03043975 |